Calculating distances in O(1)

Discussion in 'C Programming' started by racygirl, Jan 14, 2006.

  1. racygirl

    racygirl Guest

    Hi all,

    I was just wondering, is it possible to write a solution to the
    following problem with the following criteria:

    1. it must be as efficient as possible at run-time
    2. be in O(1)
    3. and be memory efficient

    The problem is:
    Find the total distance between any two cities if:
    Given
    source city destination city distance
    0 1 5
    mi.
    1 2 2
    mi.
    2 3 7
    mi.
    3 4 8
    mi.

    etc... for N cities.
    Example: distance(0, 4) = 5+2+7+8 = 22
    The distance function is being called millions and millions of times
    and the list of cities and distances do not change after the program
    starts.

    I initially thought that making an N X N matrix to store all distances
    bwteen cities would be a fast way to retrive any distace (the matrix
    would be populated as requests for distances are made), i.e. receive
    request, if request not in matrix calculate distance from array, store
    result in matrix, output result. But the N x N matrix turned out to be
    memory expensive.

    Ok. so I thought a hash table with a linked list (for collisions) would
    solve my memory problem, but I'm not sure whether or not it satisfies
    all the requirements for this solution...

    What do you guys think?
    racygirl, Jan 14, 2006
    #1
    1. Advertising

  2. "racygirl" <> writes:
    > I was just wondering, is it possible to write a solution to the
    > following problem with the following criteria:
    >
    > 1. it must be as efficient as possible at run-time
    > 2. be in O(1)
    > 3. and be memory efficient
    >
    > The problem is:
    > Find the total distance between any two cities if:
    > Given

    [snip]
    > What do you guys think?


    I think this is a question for comp.programming. The fact that your
    question doesn't mention any particular programming language means
    it's not really a comp.lang.c question.

    If you have problems implementing a solution in C, feel free to come
    back here and ask us.


    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Jan 14, 2006
    #2
    1. Advertising

  3. racygirl wrote:
    > Hi all,
    >
    > I was just wondering, is it possible to write a solution to the
    > following problem with the following criteria:
    >
    > 1. it must be as efficient as possible at run-time
    > 2. be in O(1)
    > 3. and be memory efficient
    >
    > The problem is:
    > Find the total distance between any two cities if:
    > Given
    > source city destination city distance
    > 0 1 5
    > mi.
    > 1 2 2
    > mi.
    > 2 3 7
    > mi.
    > 3 4 8
    > mi.
    >
    > etc... for N cities.
    > Example: distance(0, 4) = 5+2+7+8 = 22


    Let's look at another example:

    Atlanta to Houston: 790 mi
    Houseton to New York: 1610 mi
    New York to Norfolk: 370 mi

    By your logic, the distance between Atlanta to Norfolk would be 2770
    mi, while it is actually about 560 mi.

    The problem you describe is usually solved by storing the position of
    each city, say the latitude and longitude, then calculating the
    distance between the two positions. This way all you need to do is
    look up the two positions and perform the distance calculation.

    As for the computational complexity, if you were to always refer to the
    cities as numbers that could be used as indices into an array you could
    make this lookup O(1). To be useful though you will probably need to
    be able to look up city names which can easily be done in O(log n) time
    using a tree structure (pick one), hashing could provide close to O(1),
    perfect hashing real O(1).

    Did you have a C question?

    Robert Gamble
    Robert Gamble, Jan 14, 2006
    #3
  4. racygirl

    Chuck F. Guest

    racygirl wrote:
    >
    > I was just wondering, is it possible to write a solution to the
    > following problem with the following criteria:
    >
    > 1. it must be as efficient as possible at run-time
    > 2. be in O(1)
    > 3. and be memory efficient
    >
    > The problem is:
    > Find the total distance between any two cities if:
    > Given
    > source city destination city distance
    > 0 1 5 mi.
    > 1 2 2 mi.
    > 2 3 7 mi.
    > 3 4 8 mi.
    >
    > etc... for N cities.
    > Example: distance(0, 4) = 5+2+7+8 = 22 The distance function is
    > being called millions and millions of times and the list of
    > cities and distances do not change after the program starts.
    >
    > I initially thought that making an N X N matrix to store all
    > distances bwteen cities would be a fast way to retrive any
    > distace (the matrix would be populated as requests for distances
    > are made), i.e. receive request, if request not in matrix
    > calculate distance from array, store result in matrix, output
    > result. But the N x N matrix turned out to be memory expensive.
    >
    > Ok. so I thought a hash table with a linked list (for
    > collisions) would solve my memory problem, but I'm not sure
    > whether or not it satisfies all the requirements for this
    > solution...
    >
    > What do you guys think?


    I have quoted the entire thing. First, it is highly off-topic for
    c.l.c, as it deals with algorithms, not the c language. Cross
    posted to comp.programming with F'UPs set. Go there for any more.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
    More details at: <http://cfaj.freeshell.org/google/>
    Chuck F., Jan 14, 2006
    #4
  5. racygirl

    racygirl Guest

    yeah, not really a language question... thanks any way.
    racygirl, Jan 14, 2006
    #5
  6. racygirl

    racygirl Guest

    Hi Robert,
    Thank you for your help, my problem is actually simpler than that, i'm
    given only the distance from one city to the next ordered by city
    number. Mark P from another group had a clever idea: "compute all
    distances from city 0 to every city, d. To find the distance from i
    to j do d[j] - d. " which executes in O(1) at run time with O(n)
    memory.

    clever huh?
    racygirl, Jan 14, 2006
    #6
  7. In article <>,
    racygirl <> wrote:
    >Hi Robert,


    Robert who? Please give appropriate attributation, and please
    quote sufficient previous material to establish context.

    >Thank you for your help, my problem is actually simpler than that, i'm
    >given only the distance from one city to the next ordered by city
    >number. Mark P from another group had a clever idea: "compute all
    >distances from city 0 to every city, d. To find the distance from i
    >to j do d[j] - d. " which executes in O(1) at run time with O(n)
    >memory.


    >clever huh?


    The problem is so artificial as to appear to be a school
    assignment. Because of that, I will not give a solution,
    but I will point out that the above algorithm is broken,
    as it does not take into account arithmetic overflow in
    the sum of the distances.
    --
    Programming is what happens while you're busy making other plans.
    Walter Roberson, Jan 14, 2006
    #7
  8. racygirl

    Bart Guest

    Walter Roberson wrote:
    > In article <>,
    > racygirl <> wrote:


    > >number. Mark P from another group had a clever idea: "compute all
    > >distances from city 0 to every city, d. To find the distance from i


    > The problem is so artificial as to appear to be a school
    > assignment. Because of that, I will not give a solution,
    > but I will point out that the above algorithm is broken,
    > as it does not take into account arithmetic overflow in
    > the sum of the distances.


    Overflow? How many cities are going to be more than 32767 miles apart?
    (Or 2 billion miles on most PCs). Maybe in millimetres there might be a
    problem.


    bart
    Bart, Jan 14, 2006
    #8
  9. racygirl

    Michael Mair Guest

    Bart wrote:
    > Walter Roberson wrote:
    >
    >>In article <>,
    >>racygirl <> wrote:

    >
    >
    >>>number. Mark P from another group had a clever idea: "compute all
    >>>distances from city 0 to every city, d. To find the distance from i

    >
    >
    >>The problem is so artificial as to appear to be a school
    >>assignment. Because of that, I will not give a solution,
    >>but I will point out that the above algorithm is broken,
    >>as it does not take into account arithmetic overflow in
    >>the sum of the distances.

    >
    > Overflow? How many cities are going to be more than 32767 miles apart?
    > (Or 2 billion miles on most PCs). Maybe in millimetres there might be a
    > problem.


    32767 millimetres = 32 metres. Sounds like conurbation.
    2E9 millimetres = 2E6 metres = 2E3 kilometres. Feasible.

    Apart from that, int was never mentioned.


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Jan 14, 2006
    #9
  10. In article <>,
    Bart <> wrote:

    >Walter Roberson wrote:


    >> The problem is so artificial as to appear to be a school
    >> assignment. Because of that, I will not give a solution,
    >> but I will point out that the above algorithm is broken,
    >> as it does not take into account arithmetic overflow in
    >> the sum of the distances.


    >Overflow? How many cities are going to be more than 32767 miles apart?
    >(Or 2 billion miles on most PCs). Maybe in millimetres there might be a
    >problem.


    If I were creating an assignment for a class that was required
    to have certain behaviours, I would likely create test-case
    drivers to be run through automatically -- and I wouldn't hesitate to
    put in a test case that included very large distances, alongside
    test cases that input negative numbers, strings, empty lines, and
    so on.

    --
    "No one has the right to destroy another person's belief by
    demanding empirical evidence." -- Ann Landers
    Walter Roberson, Jan 14, 2006
    #10
  11. >Let's look at another example:
    >
    >Atlanta to Houston: 790 mi
    >Houseton to New York: 1610 mi
    >New York to Norfolk: 370 mi
    >
    >By your logic, the distance between Atlanta to Norfolk would be 2770
    >mi, while it is actually about 560 mi.


    The first example may be correct, if you're talking about airline
    miles rather than as-the-missile-flies distances.

    >The problem you describe is usually solved by storing the position of
    >each city, say the latitude and longitude, then calculating the
    >distance between the two positions. This way all you need to do is
    >look up the two positions and perform the distance calculation.


    Unfortunately, it's not possible to GET a (nonstop) commercial
    flight from Airport A to Airport B for all possible pairs of A and
    B. Things such as the Wright Amendment make certain (commercial)
    flights illegal, and others just don't have enough traffic to make
    them worthwhile. Also, some airports may not be able to handle all
    flights (an intercontinental flight from Paris, France to Northwest
    Pothole, Texas may find the runways too short for anything but crop
    dusters to land).

    Gordon L. Burditt
    Gordon Burditt, Jan 14, 2006
    #11
  12. racygirl

    racygirl Guest

    Whatever
    racygirl, Jan 17, 2006
    #12
  13. racygirl

    Chuck F. Guest

    racygirl wrote:
    >
    > Whatever


    I think you have been told enough times how to include proper
    context even on the google interface, and you just ignore it. I
    for one don't want to put up with these meaningless postings, so
    goodbye. PLONK (which means your posts will never reach here in
    the future).

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
    More details at: <http://cfaj.freeshell.org/google/>
    Chuck F., Jan 17, 2006
    #13
  14. racygirl

    Default User Guest

    racygirl wrote:

    > Whatever


    *plonk*



    Brian
    Default User, Jan 17, 2006
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Lozzi

    zip code and distances

    David Lozzi, Feb 18, 2005, in forum: ASP .Net
    Replies:
    6
    Views:
    2,101
    =?Utf-8?B?U2FuZHk=?=
    Jun 23, 2005
  2. tienlx
    Replies:
    0
    Views:
    318
    tienlx
    Jun 1, 2006
  3. Hul Tytus
    Replies:
    1
    Views:
    392
    Ben Pfaff
    Feb 16, 2005
  4. Replies:
    1
    Views:
    897
    Nanda Lella[MSFT]
    Dec 4, 2007
  5. John
    Replies:
    11
    Views:
    244
    Dave Bass
    May 25, 2008
Loading...

Share This Page