Get multiple elements from a list by indices at a constant time
What is the best way to get multiple elements from a list by their indices at constant time?
If I have an array:
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
And I have a list / array with indices:
List<Integer> indices = new ArrayList<>();
indices.add(0);
indices.add(2);
indices.add(3);
How can I get a, c, d in constant time? I need something like this:
List<String> filtered = list.filterByIndex(indices);
filtered.stream().forEach(x -> System.out.print(x));
// output:"acd"
UPDATE: Seal of items does not have to be in constant time, but only when collecting items. The above code for printing items is for demonstration purposes only.
source to share
I suggest:
List<String> filtered = indices.stream()
.map(list::get)
.collect(Collectors.toList());
The result will be:
[a, c, d]
Assuming the list has constant access (as it is ArrayList
), this is done in time that is linear in the number of items requested (length indices
), but does not increase with the length of the list list
. As stated in the comments, this is the best we can do.
Edit: To be honest, I don't know if the collection step is higher in linear time for the number of items collected. Probably an increase in the load time of the list, and it probably won't take more linear time. If we need to be sure, we need to collect this path instead:
.collect(Collectors.toCollection(() -> new ArrayList<>(indices.size())));
This will ensure that the list with the appropriate capacity is highlighted from the start, so no extensions are required.
source to share
To create a list:
List<String> filtered = new ArrayList<>();
indices.forEach(index -> filtered.add(list.get(index)));
System.out.println(filtered);
Stream and map solution
List<String> filtered = indices.stream()
.map(index -> list.get(index))
.collect(Collectors.toList());
If you only want a string, you can do it with StringBuilder
StringBuilder sb = new StringBuffer();
indices.forEach(index -> sb.append(list.get(index)));
System.out.println(sb.toString());
source to share