Geek asks and answers

What is the most efficient way to insert a string into an already sorted list of string arrays?

I have an ArrayList that has 17,000 words in it. I need to add a word to the list only if it is not already included, and I need to keep the sort order of the list. those. I need to put it in its correct location in alphabetical order.

I do not know how to find the right place to insert it. I use binary search to find if a word is in the list and returns the index if it is there, or -1 if it is not. I planned to use ArrayList.add (int index, element E) to place it.

+5
source share
6 answers

Convert ArrayListto TreeSet http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

TreeSet will take care of duplicates for you and save the words in alphabetical order.

Example: ( WordList- these are ArrayListwords)

TreeSet<String> WordSet = new TreeSet<String>(WordList);
+3
source

Use the inline method binarySearch. If the key is not found, the return number is-(insertionIndex) - 1

+2
source

, api ,

, 2 , , == . ==, . , java , . , - :

(bool, int) binSearch(IList list)
  returns true, -1 if found
  returns false, higher of 2 bounds otherwise

, java,

+1

, , . , , .

, . , , - , ​​ .

+1

, , . . , ArrayList, :

ArrayList indexes;
indexes[0] = {"a", 0};
indexes[1] = {"b", 123};
...

, "a", 0-123.

0

If the words are not repeated as you say, you might consider using trie . Inserting operations on trie is somewhat faster than in the hash table, because there are no collisions. The same is true for the search.

In addition, ArrayListto insert an element in the middle of the list, this means rearranging half the elements or increasing the size of the array, which can be somewhat expensive.

If you're interested, you can see the implementation on the following page: https://forums.oracle.com/forums/thread.jspa?messageID=8787521

0
source

More articles:


All Articles