Efficient way to compare lots of items

[Bregor]

Hi,

 

is there a way to compare lots of items fast and correct other than probing each item with isItemEqual.

 

As far as I know there is no override for hashCode/equals for items.

 

I thought about using itemId and damage for this purpose (according to writeToNBT both are shorts and could combined into an int as a form of hash code), but getting the item ID doesn't seem to be very efficient with 1.7.

 

How do you test an item against a large list of possible items, like for an item storage system?

[jabelar]

While it is good to be worried about efficiency, do you already know you have a problem with perf or are you just worrying about it?

 

A few things to think about:

 

You should organize any series of tests by how likely they are to happen to stop the tests as early as possible.  Basically test the least likely first.  Imagine you have code that needs to check if you're walking on grass and holding a "grass staff" item.  Walking on grass happens a lot, but presumably holding a grass staff would only be occasional. So it would be much faster to go if (holding grass staff) { if (walking on grass) { // do something cool here}  } than the other way around because most of the time it would only do the first test then quit.

 

The same thing happens with expressions using &&.  Java will "short circuit" (meaning quit as fast as possible) when it finds the first false part of the expression.  So holding grass staff && walking on grass is faster than the other way around.

 

Instead of equals you may also want to consider instanceof.  I'm not actually sure which is faster, but it is quite possible that instanceof is fast.

 

Lastly, in most languages switch statements can be quite efficient.  In Java though you can only switch on certain types of values, so that might limit your particular case.  Ideally you'd just switch based on the item itself, but instead you'll need to resolve it to some sort of int or similar.

 

But anyway, only optimize when you know you need to.  Otherwise you should just write well organized and straight-forward code.  Profile your code and then tackle the parts that are actually causing trouble. 

[Bregor]

Your statements are all very valid of course. But as I want to develop something like an item storage system, and I think that there O(n) vs O(log2(n)) matters.

[jabelar]

Your statements are all very valid of course. But as I want to develop something like an item storage system, and I think that there O(n) vs O(log2(n)) matters.

 

Sure, but you still need to look at it in perspective of whether that still gets to point of being a problem.  There are lots of similar sorts of algorithms going on in a video game, for example multiple entities in same area checking for collisions with each other, blocks checking for changes in neighbors, and so forth.

 

Anyway, while it is good to make the basic code efficient where you have a choice, I still think short-circuiting is the bigger band for your buck if you can find such opportunities.  I don't quite understand how an "item storage system" would create such a problem.

 

Maybe you can be more specific about the problem you're trying to solve.

[Bregor]

Anyway, while it is good to make the basic code efficient where you have a choice, I still think short-circuiting is the bigger band for your buck if you can find such opportunities.  I don't quite understand how an "item storage system" would create such a problem.

 

Maybe you can be more specific about the problem you're trying to solve.

 

Well think of a centralized storage system where you can add items to and retrieve them again - not like a chest more like Applied Energistics. There the number of different items you have to match can easily go over a few hundred (especially with enchanted stuff and other items with an NBT tag) - if every retrieval process has to lookup the required item storage location with the trivial method it means for every available item in the storage a comparison required in the worst case.

[TheGreyGhost]

Your statements are all very valid of course. But as I want to develop something like an item storage system, and I think that there O(n) vs O(log2(n)) matters.

That depends.  If you have (say) 1000 items, and you only query your items storage system a couple of times second (for example- when the player wants to retrieve an item), then I guarantee you that no-one will ever notice the difference between O(n) or O(log2(n)).

 

If you are certain you really want a faster lookup, you could place your Item into a HashMap, which is O(1) for retrieval.  It will check whether the Item object is the same instance.  If you want ItemStacks (includes damage) then your idea of using ItemID and damage as the key would also work.  ID retrieval for 1.7.2 is not slow, don't worry about that.

 

-TGG

[Nephroid]

You might want to look into a modified trie data structure. You can represent items as binary strings, and you can store integers with each state (instead of booleans).

 

It stores efficiently (memory wise) and has constant lookup and storage time (the binary strings that represent items won't grow as the number of items increase). Of course, I'm assuming that n is the number of items.

 

However, this is probably unnecessary work, and tries are limited in other ways. For example, iterating through the "elements" in a trie is a bit strange. This means that it will be a bit difficult to retrieve items from it. Sorting also isn't possible. If anything, this would be a good programming exercise, if you're interested. I can explain in more detail via PM if you want.

 

Also keep in mind that Java is a bit strange sometimes. If I recall correctly, the boolean primitive uses 8 bytes for some reason.

 

[jabelar]

Anyway, while it is good to make the basic code efficient where you have a choice, I still think short-circuiting is the bigger band for your buck if you can find such opportunities.  I don't quite understand how an "item storage system" would create such a problem.

 

Maybe you can be more specific about the problem you're trying to solve.

 

Well think of a centralized storage system where you can add items to and retrieve them again - not like a chest more like Applied Energistics. There the number of different items you have to match can easily go over a few hundred (especially with enchanted stuff and other items with an NBT tag) - if every retrieval process has to lookup the required item storage location with the trivial method it means for every available item in the storage a comparison required in the worst case.

 

So you only do the lookup when you're taking from or adding to this inventory?  I wouldn't worry much about perf as you'll be in a GUI and user can tolerate some delay.

[Nephroid]

To add, if we're strictly talking about comparison, a fast way would be to convert the items into binary strings (in integer form) and use the bitwise xor operator to see if the binary strings match. (Bitwise operations are extremely fast.) However, this probably isn't worth the work. The speed improvement, if there is any, will be negligible. Not to mention, the conversion might not be easy.

 

Also, when you bring runtime complexity into question and talk about number of items, it's no longer a question of comparison, but a question of sorting and searching.

 

If you want to compare a large number of items, you'll have to compare the same amount regardless of what comparison algorithm you chose. The search algorithm is what determines how many comparisons you do, not the comparison algorithm. So talking about O(n) vs O(log(n)) doesn't really make that much sense if you're talking about the comparison algorithm, since the size of each item is essentially bounded by a constant (unless you have tons of lists stored in NBT for a bunch of items, which is probably a design problem).

[Bregor]

So you only do the lookup when you're taking from or adding to this inventory?  I wouldn't worry much about perf as you'll be in a GUI and user can tolerate some delay.

 

No basically I am more concerned about automation as I want to supply various things from it.

 

 

Also, when you bring runtime complexity into question and talk about number of items, it's no longer a question of comparison, but a question of sorting and searching.

 

This is why I was asking for hashing I got some ideas from the comments I got here, just have to examine them.

[Nephroid]

As a side note, a comparison algorithm that performs better than O(n) cannot exist. (n is the size of the item in bits.) I'll put the reason why in spoilers if you want to think about it.

 

 

 

To confirm that two items are equal, you must somehow compare every bit of information about those two items. You can't get away with comparing less. For example, you can't say that two lists are equal if you don't compare all the elements of the lists.

 

If you're going to use a hash function, keep in mind that the hash function might get expensive. You probably don't have to worry about this; even things like AE disks (if you're planning on your system storing them) have a limited inventory (64 item types I believe), so their size is still bound by a constant.