Reversing an array

Developers Language Support
9

Yea you’re looking at O(n^2) right there.

Depends on the size of your array, but if you want uniqueness, or a lookup check I think you’re using the wrong data structure here if you want to check key uniqueness. I’d recommend using a HashMap or a Red-Black Tree and storing the data in there in the first place.

I’ll give you an example of how you can use this stable Red-Black Tree library to improve your runtime to O(n) StableRBTree/StableRBTree.mo at main · canscale/StableRBTree · GitHub


type Item = {
  name: Text;
  damage: Nat;
};

type Count = Nat;

let itemBackpack = RBTree.init<Item, Count>();

// this is how you seed a Red-Black Tree with your existing array of items to have an item count key value store
for (item in yourCurrentItemArray.vals()) {
  switch(RBTree.get<Item, Count>(itemBackpack, itemCompareTo, item)) {
    case null { RBTree.put<Item, Count>(item, 1) };
    case (?count) { RBTree.put<Item, Count>(item, count + 1 };
  }
};

// get unique items
let uniqueItems = Iter.filter<(Item, Count)>(
  RBTree.entries<Item, Count>(itemBackpack),
  func((item, count)) { count == 1 }
);

Another approach would be to just use a HashMap for even quicker lookups. Keep in mind that HashMaps are O(1), but aren’t nearly as memory efficient as Red-Black Trees. The Motoko HashMap implementation has been rumored to take up 28X the size