2

I'm working on an update process which inserts items into a sorted list, and processes those items' indices in the sorted list.

To help me with this, I created a sorted list with an "insert" method which returns the index of the new element in the list. For example, given a list of [1, 3, 5], then insert(4) will change the list to [1, 3, 4, 5] and return 2 (0-indexed). I then process the result with process(2).

Currently, when I need to do multiple updates, I do something like

for el in elements
   index = list.insert(el)
   beginUpdates()
   process(index)
   endUpdates()

In want to optimise update time by processing multiple indices in a single update. Of course, the following would be incorrect:

indices = []
for el in elements
   indices.append(list.insert(el))
beginUpdates()
for index in indices
   process(index)
endUpdates()

because each insert could invalidate a previously-calculated index. For example:

list = [1, 3, 5]
index1 = list.insert(4) // index of 4: 2
index2 = list.insert(2) // index of 4: 3

Now, if I process(index1), it will process the wrong index.

So I think that, in the same way that I can batch-process indices, I should have a method to batch-insert elements and get their correct indices. Something that will allow me to do

indices = list.batchInsert(elements)
beginUpdates()
for index in indices
   process(index)
endUpdates()

Is there an algorithm that can elegantly do this?

6
  • Wouldn't this problem go away if your process() method took the actual object as a parameter rather than an index into a list? Sep 21, 2016 at 15:43
  • process doesn't care about the object, just the index. The real-world context is an iOS collection view update, where I tell a controller that the data source changed, and which items are new. It then queries the data source for the data at the indices I provided. Sep 21, 2016 at 15:45
  • Bummer. I don't suppose you have a list.getIndexOf(element) function? Sep 21, 2016 at 15:52
  • I do (I'm working in Swift) (added that to fill out the characters, haha) Sep 21, 2016 at 15:54
  • Sometimes what I do is the very simple: after each insertion, increment each index I have so far if it is >= the latest insertion index.
    – Erik Eidt
    Sep 21, 2016 at 18:55

1 Answer 1

1

OK, so after some thinking, my colleagues and I came up with this: func insertBatch(elements: [Element]) -> [Int] { let results: [Int] = [] let sortedElements = elements.sort() for el in sortedElements { let i = insert(el) results.append(i) } return results } (Excuse the Swift :) The idea is that, since the elements to be inserted are already sorted, no specific insertion will invalidate any previously-obtained index, because they're necessarily inserted after the previous ones.

For additional optimisation, I could write an insert(minIndex: Int) function that won't try to insert the new item before minIndex, and then pass it the previous result.

Would still like to wait and see if there's a smarter solution.

2
  • This is clever, but the return indices don't correspond to the unsorted input. (This can be fixed, of course..)
    – Erik Eidt
    Sep 21, 2016 at 18:46
  • True. In my use case, it just so happens that I don't mind the order of the return indices, but I didn't state that in the question, so this answer isn't 100% correct. Sep 22, 2016 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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