| |
| |
| |
|
Page: 1 2 3 4 5 6
Comments:
<0> could get slow
<0> hehe
<1> i don't need to return the path, say 123-124-345-345763-3456
<1> i just need to know that 3456 is 4 away from 123
<2> so u need the length right?
<1> yes
<2> well as far as I can see.. ur algorithm will be teh same
<1> ah
<1> the thing is, there are around 4500 nodes or rooms
<0> :)
<2> u do know that theres plenty of info for this on the web right?
<2> shortest path algorithms
<1> hm
<2> for connected/disconnected graphs
<0> not the shortest path really
<2> well A path
<2> :)
<0> the way his data is laid out
<1> i know there are path algorithms
<1> the way it's laid out, it'd basically be searching randomly
<2> so why dont you use them?
<2> well you can just do something like this...
<0> you can have a loop :)
<2> if your dest is 999, then you search in ur db for where dest = 999
<1> right
<2> then take the source for that link and use that as a dest
<2> for your next serach
<1> how do you know the destination if you don't have a destination
<1> it just gets recursively larger
<0> start from begiing
<2> it will eventually give you teh answer as long as you don thave loops AND its a fully connected graph
<1> right
<2> Quant: doesnt really matter where u start
<1> 999 has 5 links say
<1> then each of those 5 links have 3 more
<1> and each of those have 6 more
<0> so you just need a while loop
<0> so which one of the 5 links do you use
<2> Perryman: no you just take the first one you find
<2> you dont have to do it for both
<2> if its connected and there are no loops in ur graph, you will eventually get to the starting point
<1> but if you do that you're just going randomly until you find the one you want
<0> finding shortest path would ****
<1> there are loops
<2> Perryman: yes
<1> there are MANY loops
<2> you didnt ask for the best algorithm or hte shortest one
<1> i'm asking for the fastest algorithm for the shortest path
<2> ok and what we gotta guess these things?
<0> i wouldn't use a database for this one
<2> no
<2> how many nodes do u have?
<1> 4500
<0> you should load into memory
<2> ya
<0> not a dabatase
<2> thats a very small amount of data
<0> too much overhead
<0> load from database into memory and do your searchers in your application
<1> hm
<1> that could work
<1> was thinking about making a giant table and doing lookups
<0> also
<2> you might want to also consider a different representation of the data
<0> while reading the data from the datbabase
<0> you could calcualte alot of what you need
<0> for your searches
<0> map that **** out
<2> ya
<1> here lemme see if i can show you
<1> http://www.floa.co.uk/Eve/Chaos/EVE_MAP_Chaos_Feb2004.jpg each point on that line is a number
<1> and whichever points have a line connecting them have a number also
<1> as described above
<1> and it's all in sql form
<0> damn
<1> yeah.
<2> Perryman: thats fine.. u can STORE it in the database
<2> but you work on it in memory
<2> just look up diff. data structures that will be more condusive towards whatever algorithm you might come up with
<1> it's still processing extremely slowly
<2> well you got an algorithm?
<1> it's still slow
<2> from what you told me u dont have one..
<1> oh well
<0> db isn't going to make it faster dude
<2> dude how do u know its slow?
<2> you havnt done anything
<1> eh, i'll try my best
<1> i'm not actually doing it, i'm trying to help someone else
<2> so how do u know its slow?
<1> thanks for your ideas though
<1> well, he builds DB stuff for work
<2> what data do u have that shows that he is slow?
<2> it*
<1> it taking hours to build, i guess
<2> where is the data coming from?
<1> a sql file on the computer
<2> the straight data import should be fairly quick
<2> inserting a few thousand data points takes that long? you are doing something wrong
<1> finding the shortest points does
<1> oh well
<3> what database is being used?
<2> dude ur an idiot
<2> i have asked you several times if you have an algorithm for it
<2> and u dont have one
<1> okay
<2> so how do u know finding hte shortest path takes too long?
<2> its like im talking to a brick wall
<1> for a brute force algorithm, it'd definately be too long
<2> so dont use brute force idiot
<2> geez people amaze me
<2> AND u have not tried brute force
<2> maybe it DOESNT take too long
<1> that was the method tried first
<2> try it.. that will give you some base line to compare other algorithms to
<0> you should spawn alot of threads
<0> it will be very fast
<0> each time there's a split
<0> you make threads
<0> that will go inside the splits
<2> and you keep track of what you have found so far in other tables
<2> so the future seraches will be faster
<2> theres a lot of diff things that can be done here
<1> unless it's restricted to one region, it took hours to run
<1> the data being grouped into groups of rooms with various linking points
<1> consolidating the data all into one table doesn't constrain it by nature of size
<1> but there's an extremely large number of paths
<1> and multiple paths to consider too
<1> well, i appreciate the conversation
<2> anoter thing you can do is run algorithms that will remove loops
<1> since it has to find all possible paths and find the shortest , in brute force
<4> Is there any reason why in mssql 2005, that when i run a query it works fine, but when its put in a SPROC it doesnt work anymore?
<0> great questions here :)
<2> Knave: where are you running the query?
<2> Perryman: you know that this is an NP hard problem right?
<1> yes
<2> if there was a very fast way to do this.. u would be breaking a lot of well known people claiming its NP hard
<1> he's said he's already removed loops
<2> thats the nature of hte problem.. deal with it :)
<1> ah
<2> Perryman: you told me there ar emany loops
<1> i suppose we're just going to have to limit it by distance?
<2> get the info straight man
<0> i say load it into memory
<0> then use alot of threads
<0> for each path
<1> quant: it is
<0> you can eliminate the paths with common point
<2> Quant: dont bother.. he is full of ****... he first told me theres loops in the db now hes claiming theres no loops
<0> actually no
<1> well, it seems like he's doing most of what you suggested
Return to
#sql
or
Go to some related
logs:
#debian
#politics
goal in englnd
#politics
#nhl
#visualbasic
an/aar-44
#red
#red
quote I am intrigued by your ideas, and would like to subscribe to your newslett
|
|
