Algorithm to detect enclosed space?

Page: 1 2 3
Jul 25 2013, 5:08 am
Have you actually tried mixing and matching the list procs for operators?

I.e, leaving Find() but still using +=? Like I said I haven't tested the other functions, but I'm 100% sure Add() is slower, when adding objects or not, so either something weird is happening with your code, or more likely, something else is speeding it up.
Jul 25 2013, 5:13 am
 
                           Profile results (total time)
Proc Name                          Self CPU    Total CPU    Real Time        Calls
------------------------------    ---------    ---------    ---------    ---------
/mob/verb/test                        0.158        6.057        6.057            5
/proc/IsEnclosed_1                    2.401        2.401        2.401          500
/proc/IsEnclosed_2                    1.196        1.197        1.197          500
/proc/IsEnclosed_3                    1.155        1.155        1.155          500
/proc/IsEnclosed_4                    1.147        1.147        1.147          500
/mob/player/proc/update_screen        0.000        0.000        0.000          906
/mob/player/proc/movement             0.000        0.000        0.000          906


IsEnclosed_4() uses += and -= instead of .Add and .Remove
Jul 25 2013, 5:15 am
Just out of curiosity, could you do some more digging and see which of the list functions it is that's giving an almost 50% speed increase over the operators?
Jul 25 2013, 5:20 am
Its definitely the faster .Find vs the slower "in"

                           Profile results (total time)
Proc Name                          Self CPU    Total CPU    Real Time        Calls
------------------------------    ---------    ---------    ---------    ---------
/proc/IsEnclosed_1                    4.780        4.780        4.780         1000
/proc/IsEnclosed_1b                   2.338        2.338        2.339         1000
/mob/player/proc/update_screen        0.001        0.001        0.001           92
/mob/verb/test                        0.142        7.260        0.000            1
/mob/player/proc/movement             0.000        0.000        0.000           92



proc/IsEnclosed_1b(list/search, turf/start, wall, val)
    #ifdef CRASHING
    if(!search || !start || !wall)
        CRASH("Null argument in IsEnclosed call: IsEnclosed([search], [start], [wall], [val])")
    #endif
    if(!search.Find(start)) return 0 //invalid request, start point isn't in turfs
    var/list/next = list(start) //start search from start point
    var/list/processed = list() //holds tiles that have been processed
    var/turf/t
    var/turf/t2
    while(next.len)
        t = next[1]
        if(!search.Find(t)) return 0
        for(t2 in trange(1, t))
            if(!next.Find(t2) && !processed.Find(t2))
                if(istext(wall))
                    if(t2.vars[wall] != val)
                        next += t2
                else if(istype(wall, /list))
                    if(!wall:Find(t2.type))
                        next += t2
                else if(!istype(t2, wall))
                    next += t2
        processed += t
        next -= t
    return 1
Jul 26 2013, 12:45 am
You might also want to try list associations, I noticed, oddly, that checking L[x] was faster than x in L, in one bit of test code I was working on.

I suspect that the associations use a sorted list, tree, or hash map, or some similar data structure that can be searched much faster than looping through the whole list.

It might have just been an odd case, or some slow code that made them seem faster, though.
Jul 26 2013, 12:48 am
Lummox told me that associated lists use a red-black tree (a self-balancing binary tree) a while ago, so it's probably O(log n) to find an item in an associative list. 'in' and .Find() are probably O(n), so if you've got enough things in the list associative is probably better. Use \ref[thing] as the key for thing.
Jul 26 2013, 12:57 am
Would've been cooler if there were hash tables for that amortised O(1), but I don't particularly think there's a good way to make a data structure in BYOND to do that.
Jul 26 2013, 1:01 am
Assuming reference by index is constant-time, you could do that easily. Make a list, set len to whatever size your table wants to start at, hash thing, put in table.
Jul 26 2013, 1:04 am
I don't think it is, that's the problem.
Jul 26 2013, 1:08 am
 
mob/verb/test1()
    var/list/l[10]
    for (var/i = 0 to 10000) world << l[1]
    
mob/verb/test2()
    var/list/l[100000]
    for (var/i = 0 to 10000) world << l[1]


Ran that in profiling, got essentially the same numbers for both (.706 to .697, so probably within experimental error)
Jul 26 2013, 1:08 am
In response to Jp
Are you saying... next["\ref[thing]"] = 1
Jul 26 2013, 1:09 am
In response to Jp
Well that's a nice plus.
Jul 26 2013, 1:12 am
In response to Jp
I've found that world << blah is kind of funky for profiling. There's quite a bit of time involved in the output.
Jul 26 2013, 1:12 am
 
next["\ref[t2]"] = t2
to put t2 into next.

next["\ref[t2]"]
gets t2 or null, depending on whether t2 is in next.

next.Remove("\ref[t2]")
removes t2 from next.
Jul 26 2013, 1:14 am
In response to Jp
Just as I thought... but we actually don't need to store the reference, do we? We could just check if its 1 or not. If it isn't, its either 0 or not even an entry.
Jul 26 2013, 1:14 am
In response to FIREking
FIREking wrote:
I've found that world << blah is kind of funky for profiling. There's quite a bit of time involved in the output.

mob/verb/test1()
    var/list/l[10]
    var/tot
    for (var/i = 0 to 1000000) tot += l[1]
    
mob/verb/test2()
    var/list/l[100000]
    var/tot
    for (var/i = 0 to 1000000) tot += l[1]


takes much less time (as you'd expect), but they still take approximately the same time, so I'm still confident that list access by index is constant-time.
Jul 26 2013, 1:15 am
In response to FIREking
FIREking wrote:
Just as I thought... but we actually don't need to store the reference, do we? We could just check if its 1 or not. If it isn't, its either 0 or not even an entry.

You need to be able to get the first item in the next list so you can process it. So you do need to store the item in there. (You get it by getting next[next[1]])
Jul 26 2013, 1:16 am
In response to Jp
Ah right, there's no way to "get" something if you know its "\ref[]"
Jul 26 2013, 1:18 am
In response to FIREking
FIREking wrote:
Ah right, there's no way to "get" something if you know its "\ref[]"

mob/verb/test1()
    world << locate("\ref[src]")


EDIT: Incidental: This could be very useful for making weak references, if you ever needed that functionality.
Jul 26 2013, 1:18 am
In response to Jp
Well damn. You learn something new every day.
Page: 1 2 3