Optimizing Sorting and Order Management in CoreData

Question

Sorting is an important feature in my app. I am using integers to represent the ordering sequence.

Items:        A, B, D, E, H
Order number: 0, 1, 2, 3, 4

When I insert a new item "C", here's the outcome:

Items:        A, B, C, D, E, H
Order number: 0, 1, 2, 3, 4, 5

Here's the write operation required on existing order numbers:

D: 2 -> 3
E: 3 -> 4
H: 4 -> 5

I wish to reduce the number of write operations because CoreData is pretty slow at writing. The problem becomes more significant when my users start to have a few thousand items in CoreData.

Here's my current workaround: leaving gaps between each order number. For instance:

Items:        A,  B,  D,  E,  H
Order number: 0, 10, 20, 30, 40

When I insert a new item "C", here's the outcome:

Items:        A,  B,  C,  D,  E,  H
Order number: 0, 10, 11, 20, 30, 40

No write operations are required on existing order numbers.

Every 1 or 2 weeks, when my users close the app, I run background tasks to re-arrange the gaps between order numbers so that when users insert new items, fewer existing order numbers will be affected.

Items:        A,  B,  C,  D,  E,  H
Order number: 0, 10, 20, 30, 40, 50

Since sorting is pretty common, I was thinking some of you might have a better idea on how to reduce write operations on existing order numbers.

If you have a better idea, do you mind to share it with us? Thanks.

Answer 1

In this toy application, a solution would be to translate the item value by which you are sorting to an integer and then use that to index into a Boolean array. Then your original array would look like

Items:    A, B, C, D, E, F, G, H
Present:  T, T, F, T, T, F, F, T

To insert C, you'd just change that false to true.

Now, perhaps you feel that you actually wanted help with a different application with different rules. However, you asked for help with this toy application. If you want help with a different application, you really need to tell us the rules for that application. That is the kind of help that Code Review may be more suited to provide, as there you can provide the rules in the form of a working application.

Alternately, you perhaps want some general advice.

When inserting in the middle frequently, rather than using a simple array, it is often recommended to use a linked and/or tree structure. An efficient tree structure that is stored in an array is a Heap. There are other tree structures that use pointers that are less space efficient but still time efficient.

It is common to use indexes to store order. Indexes do not need order numbers. They store order by presence instead. It is not uncommon to use a tree structure to store the index. Databases do this pretty commonly, often having multiple indexes over the same data.

CoreData is pretty slow at writing.

If you are storing enough data that this is obvious, then perhaps CoreData is the wrong solution for you.

You also might consider if you are writing individual entries directly to CoreData. In your described application, you are writing four separate values. It's possible that CoreData handles that by writing the entire array each time. If you instead work with a copy of the array, you can make all four changes and then write the entire array to CoreData once.

I don't know how CoreData works. That would be worth a question on its own if no one with the appropriate knowledge answers this one.

This is the kind of thing that you can use profiling to study. Does adding a new value to the beginning of an array take time proportional to the size of the array? If you add two items, does it take twice as long? If you work with a copy and push the whole thing, does it go back to taking the same time as a single object?