I'm creating an A* path finding system from scratch. At the moment I'm looking at the use of binary heaps to order the "open" list. I was thinking, if I have a lot of entries (hundreds possibly, but unlikely) would it be better to use a one dimensional array rather than a list object? Thanks.
Yes, it would. A 1D array is essentially a list, except the list object is a windows control and uses text, which is always slower than numbers. The array would be your best bet.
Lists are designed to dispay their content, so they are very slow even if you make them invisible.
An array is the only way to go here, I think.
You could use LB's internal list object, but I'm not sure where that is ported to and if it is designed for numbers or text or both
It would be pretty slow to create this in MMF2. Try C++.
Anyway, you could run some loop tests and see how many accesses you can do in x seconds. I'd recommend Array for this, since Internal List uses a more complex design. Saying that, it is LB's code, so it might be faster anyway.
In either case, one thing you should do is reserve space in the array before you do anything with loops. In the case of an array object, access the largest number you want. In Internal List, I think you can reserve space with a specific action. Reserving space is a must if you don't want the objects to mess about allocating new memory, copying the old memory to the new memory, and freeing the old memory, every single time you access it.
Interesting point! What would it looks like in this case of an array object?Originally Posted by Phi
Just predefine the dimensions of the array to the needed size in the frame editor,
so that it not must be resized at runtime if I use higher index values?
Predefining at edittime would be the best way, but if you have no clue about the size of the array at edittime, it's fine to simply store a value at the largest dimension. For example, if you need a 4x5x1 array (1-based), you would set the edittime values to 1x1x1, then "On x -> Set array value XY (4, 5) to 1". This will force the array object to preallocate enough space for all the 'cells' in the array up to a minimum of (4, 5).
As long as you're not making it re-allocate any more often than it should.
Note that string arrays will be slower, because the string arrays are internally values which point to memory addresses, making an array of pointers effectively. So you will pre-allocate space for the pointers, but the pointers to strings themselves (what address they point to) will still need to be allocated. There's a long, complex reason about pointers and heap/stack memory for why. Suffice it to say it'll increase the speed but allocation will be slower than number arrays.
I understand. Thank you very much for your answer. I'm using MMF for 10 years but I really don't know much about these things ... memory and such stuff. As the most MMF users I think. But for a larger project it seems to be more important as just for a small application to think about that. So it's good to have people here with deeper knowledge.
I'm not really clear about this. What do you mean?
I didn't knew that too. But it seems very important. In my smaller projects I always chose the text array because sometimes there were some strings to store and the numbers were simple to store as converted strings. Maybe it's a better solution to store strings in a different array if for example the level only needs numbers to tell the engine how it show be build.
Or maybe it's better to choose the Binary object? But I'm not sure about the used terms and how to use it. There's also no help file.
Posting Permissions
Reply With Quote