[Suggestion] [Beginner] Data structure that implements quick insertion and removal of items

Hi folks, I was wondering if it may be possible to add a data structure that would add the following points:

  • fast insertion, at most O(logn)
  • fast removal, at most O(logn)
  • fast access with subscript, at most O(logn)

While the Deque module already covers it, it gives me a bit of problems during resizes of the array, I'm using it as an underlying data structure for my app that contains approximately 200k records.

I don't want to make you lose time, as I'm a newbie in using both Git and Swift, and I'm open to suggestions, so, if you know other workarounds, I'm here to learn.

Nonetheless, here's how I would achieve my goals:

  • The data structure should be based off a SkipList, but with fixed length promotion of nodes, so that we can control where each promoted node is.
  • Each "promoted" node knows how many items are in the middle between both the previous and next node
  • Each node knows whether it is pointed by a promoted node and every promoted node points to an underlying node (This allows us a traversal between layers of "promoted" nodes)
  • Each time we add a node at a random position, we see if we have too many items, and if so, we promote a new node
  • Each time we remove a node at a random position, we see if we have too few items, and if so, we remove a promoted node
  • The search would occur by iterating from the uppest layer of promoted nodes and going down each time we would surpass our objective. Once reached, we only go down

I already worked on something my work

This started off more like a private repo for datastructures I needed.

I hope to not have angered anyone, and I'm open to suggestions and even a rejection.

Why not Dictionary?
Otherwise I'd look at some B-Tree flavour.

1 Like

Thank you for the reply.

I need to use the data inside a ForEach(), unless it’s a wrong approach, and so I need it to be conformed to the RandomAccessCollection.

Do you know if It is possible to conform a Dictionary or a B-tree to that?

If you use them inside a ForEach, I think you'd also want data to be ordered. Swift's builtin dictionary isn't, but the collections package does provide OrderedDictionary whose keys property has the random-access-collection OrderedSet type. However, I haven't looked into the complexity of the operations you outlined in the OP.

2 Likes

ForEach works with Dictionary out of the box however it indeed returns items in "arbitrary" (yet well defined) order:

ForEach(Array(dictonary.values), ...

Do you need items in a particular order (I guess you do)? If so could you tolerate spending O(N logN) to do the sort?

I don't use Algorithms package to know if B-Tree is in there (and in what form). It is not too complicated to implement but could be tricky if you never did this. It requires "<" or other form of "less" operation defined on elements and ForEach will return elements according to that. However it doesn't sound you need B-Tree, dictionary should suit you just fine. Note that SwiftUI itself may struggle with lists containing 200K elements - I guess that would be the limiting factor, not the O(N) vs O(logN) complexity.

1 Like

I've tried it, but it makes my scroll stutter. I forgot to mention that I add items while my program is running. I emulated the behavior by adding 100 items when I finish to show the ones I already had.

Would a B-tree be better?

No.

I don't know your app to suggest anything better. E.g. could you postpone adding items till after the scroll is finished?

After you tried all possible tricks like withAnimation / animation blocks, etc, you may want to consider UIKit: UICollectionView might give you better results. It's API is quite different compared to SwiftUI's List – very "manual" (more work needed and more customization possible). On the plus side it would handle much more items compared to SwiftUI, on the minus side - diffing is more problematic (you may try luck with its builtin support for diffable data sources). As a side note - you may embed UIKit views into SwiftUI app and vice versa.

OTOH have a look at this video : Building Custom Views with SwiftUI - WWDC19 - Videos - Apple Developer towards the end. This shows that very fast drawing is possible with SwiftUI.

1 Like