Velocity Reviews > Calculating distances in O(1)

# Calculating distances in O(1)

racygirl
Guest
Posts: n/a

 01-14-2006
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
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?

Keith Thompson
Guest
Posts: n/a

 01-14-2006
"racygirl" <(E-Mail Removed)> 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

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <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.

Robert Gamble
Guest
Posts: n/a

 01-14-2006
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

Chuck F.
Guest
Posts: n/a

 01-14-2006
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
> 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

racygirl
Guest
Posts: n/a

 01-14-2006
yeah, not really a language question... thanks any way.

racygirl
Guest
Posts: n/a

 01-14-2006
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[i]. To find the distance from i
to j do d[j] - d[i]. " which executes in O(1) at run time with O(n)
memory.

clever huh?

Walter Roberson
Guest
Posts: n/a

 01-14-2006
In article <(E-Mail Removed) .com>,
racygirl <(E-Mail Removed)> wrote:
>Hi Robert,

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[i]. To find the distance from i
>to j do d[j] - d[i]. " 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.

Bart
Guest
Posts: n/a

 01-14-2006

Walter Roberson wrote:
> In article <(E-Mail Removed) .com>,
> racygirl <(E-Mail Removed)> wrote:

> >number. Mark P from another group had a clever idea: "compute all
> >distances from city 0 to every city, d[i]. 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

Michael Mair
Guest
Posts: n/a

 01-14-2006
Bart wrote:
> Walter Roberson wrote:
>
>>In article <(E-Mail Removed) .com>,
>>racygirl <(E-Mail Removed)> wrote:

>
>
>>>number. Mark P from another group had a clever idea: "compute all
>>>distances from city 0 to every city, d[i]. 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.

Walter Roberson
Guest
Posts: n/a

 01-14-2006
In article <(E-Mail Removed) .com>,
Bart <(E-Mail Removed)> 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