473,574 Members | 2,627 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Calculating distances in O(1)

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?

Jan 14 '06 #1
13 2052
"racygirl" <ra******@hotma il.com> 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.programmin g. 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_Keit h) ks***@mib.org <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.
Jan 14 '06 #2
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

Jan 14 '06 #3
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.programmin g with F'UPs set. Go there for any more.

--
"If you want to post a followup via groups.google.c om, 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/>
Jan 14 '06 #4
yeah, not really a language question... thanks any way.

Jan 14 '06 #5
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?

Jan 14 '06 #6
In article <11************ **********@g43g 2000cwa.googleg roups.com>,
racygirl <ra******@hotma il.com> 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[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.
Jan 14 '06 #7

Walter Roberson wrote:
In article <11************ **********@g43g 2000cwa.googleg roups.com>,
racygirl <ra******@hotma il.com> 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

Jan 14 '06 #8
Bart wrote:
Walter Roberson wrote:
In article <11************ **********@g43g 2000cwa.googleg roups.com>,
racygirl <ra******@hotma il.com> 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.
Jan 14 '06 #9
In article <11************ **********@g14g 2000cwa.googleg roups.com>,
Bart <bc@freeuk.co m> 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
Jan 14 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
4098
by: Jayne Wolps | last post by:
Hello I wonder if anyone can help. I would like to know how certain sites: http://aboutbritain.com/ArundelCastle.htm, and http://travel.knowhere.co.uk/place/+bristol-0/ manage to put approx mile distances between their listed towns and attractions. You will see it on the knowhere.co.uk site on the right side where they list nearby towns...
5
8797
by: Ron Adam | last post by:
Hi, I'm having fun learning Python and want to say thanks to everyone here for a great programming language. Below is my first Python program (not my first program) and I'd apreciate any feedback on how I might do things differently to make it either more consice, readable, or faster. ie... are there better ways to do it in Python? It...
0
2263
by: Kasp | last post by:
Hi there, I am trying to make an OLAP cube on a table having two columns (datetime, Number_of_times_an_event_occured). My dimension is time and I want to measure the Min and Max times an event occured over time. I have no problem in calculating Maximum occurance of events over time. However, I have some NULL values in my...
1
3235
by: Joe Bongiardina | last post by:
What does the message "calculating...." mean in the lower left status area of a form? I have a form with no calculated, concatenated or lookup fields, yet it displays this msg. The form takes forever to open and I'm wondering what it's "calculating" and if that's the bottleneck. Thanks.
1
2368
by: jlm | last post by:
I have a form which feeds table (TblEmpLeave) of Employee Leave Time (time taken off for Administrative, Annual, Sick, Compensation leave). I have EmpID, LeaveDate, LeaveType, LeaveHours fields on this form. Any employee can have multiple entries in the table (key fields are EmpID and LeaveID) for multiple dates (John Doe can take 3 days...
0
1777
by: robin9876 | last post by:
In an Access 2000 database on some forms 'Calculating...' is continuously displayed in the status bar window and the text of the control is automatically selected. The only workaround is switching to another application and back between each field that data is entered. I have tried this database on pc's that have office 2000 SP1a and SP3....
1
1582
by: Hul Tytus | last post by:
comp.lang.c converting a point known by 4 distances to xyz coordinates? Amongst all the librarys on the internet there is certainly source for a routine that converts a point known by 4 distances from 4 known points to common xyz coordinates. Anyone know where it is? Hul -- - for email, put the word "keeper" in the subject line -
0
912
by: tienlx | last post by:
Hi, I've a report (ReportAppointment.rdlc) in ASP.NET When viewing reports, the vertical distance between the two group are too big. I've tried to reduce the vertical distances but i can't. Demo: http://server4.pictiger.com/img/331901/picture-hosting/demo.jpg http://server4.pictiger.com/img/336484/picture-hosting/report.jpg
3
2585
by: Paul Aspinall | last post by:
Hi Can anyone recommend a suitable way of calculating distances between UK post codes?? Many websites do this, and I'm wondering if there is some standard code, and where the reference DB comes from? Any help/advice appreciated Thanks
0
7737
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
1
7827
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8109
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6471
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5632
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5316
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3752
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3762
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2253
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.