What is the clearest explanation of what computer scientists mean by "the naive implementation"? I need a good clear example which will illustrate — ideally, even to non-technical people — that the naive implementation may technically be a functioning solution to the problem, but practically be utterly unusable.
Antaeus Feldspar
问问题
10537 次
15 回答
75
I'd try to keep it away from computers altogether. Ask your audience how they find an entry in a dictionary. (A normal dictionary of word definitions.)
The naive implementation is to start at the very beginning, and look at the first word. Oh, that's not the word we're looking for - look at the next one, etc. It's worth pointing out to the audience that they probably didn't even think of that way of doing things - we're smart enough to discount it immediately! It is, however, about the simplest way you could think of. (It might be interesting to ask them whether they can think of anything simpler, and check that they do really understand why it's simpler than the way we actually do it.)
The next implementation (and a pretty good one) is to start in the middle of the dictionary. Does the word we're looking for come before or after that? If it's before, turn to the page half way between the start and where we are now - otherwise, turn to the page half way between where we are now and the end, etc - binary chop.
The actual human implementation is to use our knowledge of letters to get very rapidly to "nearly the right place" - if we see "elephant" then we'll know it'll be "somewhere near the start" maybe about 1/5th of the way through. Once we've got to E (which we can do with very, very simple comparisons) we find EL etc.
于 2008-11-02T20:52:13.817 回答
9
StackOverflow 的 Jeff Atwood 有一个与洗牌数组相关的简单算法的一个很好的例子。
于 2008-11-02T20:59:03.850 回答
8
Doing it the most straightforward, least tricky way available. One example is selection sort.
In this case naive does not mean bad or unusable. It just means not particularly good.
Taking Jon Skeet's advice to heart you can describe selection sort as:
- Find the highest value in the list and put it first
- Find the next highest value and add it to the list
- Repeat step 2 until you run out of list
It is easy to do and easy to understand, but not necessarily the best.
于 2008-11-02T20:49:24.103 回答
4
another naive implementation would be the use of recursion in computing for an integer's factorial in an imperative language. a more efficient solution in that case is to just use a loop.
于 2008-11-03T08:28:24.533 回答
2
“朴素实施”几乎总是与“蛮力实施”同义。幼稚的实现通常是直观的，并且是第一个想到的，但也通常是 O(n^2) 或更糟，因此对于大输入来说花费太长时间太不实用。
编程竞赛充满了问题，其中天真的实现无法在可接受的时间内运行，问题的核心是提出一种改进的算法，该算法通常不那么明显，但运行速度更快。
于 2009-08-24T20:20:50.830 回答
2
你能想到的最明显、最简单的求幂算法是什么？
base ** exp是base * base * ... * base，exp次：
double pow(double base, int exp) {
double result = 1;
for (int i = 0; i < exp; i++)
result *= base;
return result;
}
但是，它不处理负指数。记住base ** exp == 1 / base ** (-exp) == (1 / base) ** (-exp)：
double pow(double base, int exp) {
double result = 1;
if (exp < 0) {
base = 1 / base;
exp = -exp;
}
for (int i = 0; i < exp; i++)
result *= base;
return result;
}
不过，实际上可以base ** exp用少于exp乘法来计算！
double pow(double base, int exp) {
double result = 1;
if (exp < 0) {
base = 1 / base;
exp = -exp;
}
while (exp) {
if (exp % 2) {
result *= base;
exp--;
}
else {
base *= base;
exp /= 2;
}
}
return result * base;
}
这利用了base ** exp == (base * base) ** (exp / 2)ifexp是偶数的事实，并且只需要log2(exp)乘法。
于 2008-11-03T15:58:12.160 回答
2
我花时间仔细阅读了你的问题，我有一个完美的例子。
一个很好的清晰示例将说明 - 理想情况下，即使对非技术人员也是如此 - 幼稚的实现在技术上可能是解决问题的有效解决方案，但实际上完全无法使用。
试试Bogosort吧！
如果使用 bogosort 对一副纸牌进行排序，它将包括检查纸牌是否有序，如果不是，则将纸牌扔到空中，随机捡起纸牌，然后重复该过程直到甲板被分类。
于 2008-11-03T16:28:23.833 回答
2
天真的实现是：
- 直觉的;
- 首先想到的；
- 经常有感染力和/或有问题的角落案例；
于 2010-01-20T10:05:20.550 回答
1
Determining if a number is prime or not (primality test) is an excellent example.
The naive method just check if n mod x where x = 2..square root(n) is zero for at least one x. This method can get really slow for very large prime numbers and it is not feasible to use in cryptography.
On the other hand there are a couple of probability or fast deterministic tests. These are too complicated to explain here but you might want to check the relevant Wikipedia article on the subject for more information: http://en.wikipedia.org/wiki/Primality_test
于 2008-11-02T20:49:30.170 回答
1
Let's say that someone figures out how to extract a single field from a database and then proceeds to write a web page in PHP or any language that makes a separate query on the database for each field on the page. It works, but will be incredibly slow, inefficient, and difficult to maintain.
于 2008-11-02T20:51:16.297 回答
1
天真并不意味着不好或无法使用 - 它意味着具有某些品质，这些品质会在特定环境和特定目的中造成问题。
经典的例子当然是排序。在对包含十个数字的列表进行排序的情况下，任何旧算法（除了 pogo 排序）都可以很好地工作。但是，当我们达到数千个或更多数字的规模时，通常我们会说选择排序是一种朴素算法，因为它具有 O(n^2) 时间的质量，这对于我们的目的来说太慢了，而且非朴素算法是快速排序，因为它具有 O(n lg n) 时间的质量，这对于我们的目的来说足够快。
事实上，在对包含十个数字的列表进行排序的情况下，快速排序是一种简单的算法，因为它比选择排序需要更长的时间。
于 2008-11-02T20:59:30.573 回答
0
Bubble sort over 100,000 thousand entries.
于 2008-11-02T20:48:27.223 回答
0
（还没有看到发布的真正幼稚的实现，所以......）
以下实现是“幼稚的”，因为它不涵盖边缘情况，并且在其他情况下会中断。它非常易于理解，并且可以传达编程信息。
def naive_inverse(x):
return 1/x
它会：
- 中断 x=0
- 传递整数时做得不好
您可以通过添加这些功能使其更加“成熟”。
于 2008-11-02T21:59:52.447 回答
-5
A O(n!) algorithm.
foreach(object o in set1)
{
foreach(object p in set1)
{
// codez
}
}
This will perform fine with small sets and then exponentially worse with larger ones.
Another might be a naive Singleton that doesn't account for threading.
public static SomeObject Instance
{
get
{
if(obj == null)
{
obj = new SomeObject();
}
return obj;
}
}
If two threads access that at the same time it's possible for them to get two different versions. Leading to seriously weird bugs.
于 2008-11-02T20:48:53.900 回答