11
\$\begingroup\$

I have \$k\$ sorted Lists, each of size \$n\$. Currently I have hard-coded 5 sorted Lists each of size 3, but in general that is configurable.

I would like to search for single element in each of the \$k\$ Lists (or its predecessor, if it doesn't exist).

Obviously I can binary search each List individually, resulting in a \$O(k*log(n))\$ runtime. But I think we can do better than that: after all, we're doing the same search \$k\$ times.

Could this be improved?

private static TreeSet<Integer> tree = new TreeSet<Integer>();

public SearchItem(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        tree.addAll(input);
    }
}

public Integer getItem(final Integer x) {
    if(tree.contains(x)) {
        return x;
    } else {
        return tree.higher(x);
    }
}

public static void main(String[] args) {
    List<List<Integer>> lists = new ArrayList<List<Integer>>();

    List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 6));
    List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    List<Integer> list3 = new ArrayList<Integer>(Arrays.asList(2, 3, 6));
    List<Integer> list4 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    List<Integer> list5 = new ArrayList<Integer>(Arrays.asList(4, 8, 13));

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);
    lists.add(list4);
    lists.add(list5);

    SearchItem search = new SearchItem(lists);
    System.out.println(tree);

    Integer dataOuput = search.getItem(5);

    System.out.println(dataOuput);
}
\$\endgroup\$
  • \$\begingroup\$ Question: In your text you say: I would like to search for single element in each of the k Lists (or its predecessor, if it doesn't exist). but in your code you get the `*successor* not the predecessor. Which one is right? \$\endgroup\$ – rolfl Feb 28 '14 at 2:00
  • \$\begingroup\$ @rolfl: I just updated the question.. I miss couple of important points.. I have rewrote most of the things.. Now take a look.. It will make sense now.. I guess now you will be angry as in the question lot of things might have change as corresponding to what you have suggested :( \$\endgroup\$ – david Feb 28 '14 at 3:05
8
\$\begingroup\$

I think you have some misguided assumptions here.

For a start, what you have now is not \$O(k \log(n))\$, it first scans and sorts all the data in to the tree, which is a \$O(N \log(N))\$ operation, where \$N\$ is the cumulative data size (sum of input-array sizes). Then, the check on it, is a \$O(\log(N))\$ check, so, your algorithm is in the order of \$O(N\log(N))\$.

The complexity you are worried about \$O(k\log(n))\$ is really quite trivial. \$k\$ is a small number (5), and log(n) is always small... in many ways, after n = 128 it is effectively a constant....

So, I would do the following:

  1. binary search each List
  2. keep the 'min' value

with the code:

Integer result = null;
for (List<Integer> data : lists) {
    int pos = Collections.binarySearch(data, input);
    if (pos >= 0) {
        //exact match, return
        return data.get(pos);
    }
    pos = -pos - 1;
    if (pos < data.size()) {
        Integer found = data.get(pos);
        if (result == null || result.compareTo(found) > 0) {
            result = found;
        }
    }
}
return result;

Now, if you wanted to be fancy, and you wanted the fastest response times, you could put each binary search in to a Callable<Integer>, and run them in parallel....

Then rank the results, and teturn it all in time complexity \$O(\log(n))\$ assuming \$k\$ is less than your hardware CPU count.

\$\endgroup\$
5
\$\begingroup\$

Two quick notes about the code in the question:

  1. A bug: a client could create more than one instance of the class but all of them will use the same TreeSet instance since it's static.

  2. public Integer getItem(final Integer x) {
        if(tree.contains(x)) {
            return x;
        } else {
            return tree.higher(x);
        }
    }
    

    The following is the same:

    public Integer getItem(final Integer x) {
        return tree.ceiling(x);
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.