计算距离O（1） [英] Calculating distances in O(1)
问题描述
大家好，
我只是想知道，是否有可能使用以下标准为
以下问题编写解决方案：
1.它必须在运行时尽可能高效
2.在O（1）
3.并且是内存效率很高
问题是：
如果出现以下情况，请查找任意两个城市之间的总距离：
给定
来源城市目的地城市距离
0 1 5
mi。
1 2 2
mi。
2 3 7
mi。
3 4 8
mi。
等...适用于N个城市。
例如：距离（0,4）= 5 + 2 + 7 + 8 = 22
距离函数是被称为数百万和数百万次
以及城市和城市名单程序结束后距离不会改变
开始。
我最初认为制作一个NXN矩阵来存储所有距离
bwteen城市将是一个快速的方式来回溯任何distace（矩阵
将填充作为距离请求），即接收
请求，如果请求不在矩阵计算距离数组，商店的距离
导致矩阵，输出结果。但N×N矩阵原来是昂贵的内存。
好的。所以我认为带有链表的哈希表（用于碰撞）将会解决我的记忆问题，但是我不确定它是否满足
所有的这个解决方案的要求...
你们怎么想？
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" < RA ****** @ hotmail.com>写道：
"racygirl" <ra******@hotmail.com> writes:
我只是想知道，是否可以按照以下标准编写以下问题的解决方案：
1.它必须同样高效尽可能在运行时
2.在O（1）
3.并记忆效率
问题是：
找到任何之间的总距离两个城市如果：
给出
[snip]你们怎么想？
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?
我认为这是comp.programming的问题。你的
问题没有提到任何特定的编程语言这一事实意味着
它不是真正的comp.lang.c问题。
如果您在使用C语言实现解决方案时遇到问题，请随时回复
并告诉我们。
-
Keith Thompson（The_Other_Keith） ks***@mib.org < http：//www.ghoti.net/~ kst>
圣地亚哥超级计算机中心< *> < http://users.sdsc.edu/~kst>
我们必须做点什么。这是事情。因此，我们必须这样做。
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) 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.
racygirl写道：
racygirl wrote:
大家好，
我只是想知道，是可以使用以下标准编写以下问题的解决方案：
1.它必须在运行时尽可能高效
2.在O（ 1）
3.内存高效
问题是：
如果出现以下情况，请查看任意两个城市之间的总距离：
给出来源城市目的地城市距离
0 1 5
mi。
1 2 2
mi。
2 3 7
mi。
3 4 8
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
让我们来看看另外一个例子：
亚特兰大到休斯敦：790英里
Houseton到纽约：1610英里
纽约到诺福克：370 mi
按照你的逻辑，亚特兰大到诺福克的距离是2770
mi，而实际上是560英里。
你描述的问题通常是通过存储每个城市的位置
来解决，比如经纬度，然后计算两者之间的
距离位置。这样你需要做的就是
查找两个位置并执行距离计算。
至于计算复杂性，如果你总是将
城市称为可以作为数组索引的数字，你可以使用
进行查找O（1）。为了有用虽然你可能需要
能够查找城市名称，这可以在O（log n）时间内轻松完成
使用树形结构（选择一个），哈希可以提供接近O（1），
完美哈希真实O（1）。
你有C问题吗？ />
Robert Gamble
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
racygirl写道：
racygirl wrote:
我只是想知道是否有可能使用以下标准为以下问题编写解决方案：
1.它必须在运行时尽可能高效
2.在O（1）
3.并且记忆效率很高
问题是：
如果出现以下情况，请查找任意两个城市之间的总距离：
来源
城市目的地城市距离
0 1 5 mi。
1 2 2 mi。
2 3 7 mi。
3 4 8英里。
等...适用于N个城市。
示例：距离（0,4）= 5 + 2 + 7 + 8 = 22距离函数是
在程序启动后，数百万次，并且城市和距离列表不会改变。
我最初认为制作一个NXN矩阵来存储所有的距离bwteen城市将是一个快速的方式来回溯任何
distace（矩阵将填充作为距离的请求
），即接收请求，如果请求不在矩阵中
计算距离数组，将结果存储在矩阵中，输出结果。但是N x N矩阵的内存非常昂贵。
好的。所以我认为带有链表的哈希表（用于
冲突）可以解决我的记忆问题，但是我不确定它是否满足这个解决方案的所有要求...
你们觉得怎么样？
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?
我引用了整个事情。首先，对于
c.l.c来说，它是非常偏离主题的，因为它处理的是算法，而不是c语言。交叉
发布到comp.programming并设置了F''UPs。再去那里。
-
"如果你想通过groups.google.com发布一个后续，不要用
破损的回复链接在文章的底部。点击
" show options"在文章的顶部，然后点击
回复在文章标题的底部。 - Keith Thompson
详情请见：< http://cfaj.freeshell.org/google/>
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/>
这篇关于计算距离O（1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
