34

コンピュータ科学者が「ナイーブな実装」を意味することの最も明確な説明は何ですか? 単純な実装が技術的には問題の機能的な解決策になる可能性があるが、実際にはまったく使用できないことを (理想的には、技術者ではない人にも) 説明する明確な例が必要です。

4

15 に答える 15

75

私はそれをコンピュータから完全に遠ざけようとします。聴衆に辞書のエントリをどのように見つけるかを尋ねます。(単語定義の通常の辞書。)

単純な実装は、最初から開始し、最初の単語を確認することです。ああ、それは私たちが探している言葉ではありません - 次の言葉などを見てください。聴衆に、彼らはおそらくそのようなやり方を考えさえしなかったことを指摘する価値があります - 私たちはそれを軽視するのに十分賢いです.すぐに！ただし、考えられる最も簡単な方法についてです。(もっと簡単なことを考えられるかどうかを尋ねて、実際に行う方法よりも簡単な理由を本当に理解しているかどうかを確認するのは興味深いかもしれません。)

次の実装 (そしてかなり良い実装) は、辞書の途中から開始することです。探している単語はその前か後か？以前の場合は、開始位置と現在位置の中間にあるページに移動します。そうでない場合は、現在位置と終了位置の中間にあるページに移動します。バイナリ チョップ。

実際の人間の実装は、文字の知識を使用して、「ほぼ適切な場所」に非常に迅速に到達することです。「象」を見れば、それが「最初のどこか」にあることがわかります。通り抜けます。E にたどり着くと (これは非常に単純な比較で行うことができます)、EL などを見つけます。

于 2008-11-02T20:52:13.817 に答える
9

StackOverflow の Jeff Atwood は、配列のシャッフルに関連する単純なアルゴリズムの素晴らしい例を示しました。

于 2008-11-02T20:59:03.850 に答える
8

利用可能な最も簡単で、最もトリッキーな方法でそれを行います。その一例が選択ソートです。

この場合、ナイーブは悪いとか使えないという意味ではありません。特に良くないという意味です。

Jon Skeetのアドバイスを心に留めて、選択ソートを次のように説明できます。

  1. リスト内で最も高い値を見つけて最初に置きます
  2. 次に高い値を見つけてリストに追加します
  3. リストがなくなるまでステップ 2 を繰り返します

実行は簡単で理解しやすいですが、必ずしも最善であるとは限りません。

于 2008-11-02T20:49:24.103 に答える
4

別の単純な実装は、命令型言語で整数の階乗を計算する際に再帰を使用することです。その場合のより効率的な解決策は、ループを使用することです。

于 2008-11-03T08:28:24.533 に答える
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

「素朴な実装」は、ほとんどの場合、「ブルートフォース実装」と同義です。単純な実装は、多くの場合直感的で最初に頭に浮かびますが、多くの場合 O(n^2) またはそれよりも悪いため、大きな入力には時間がかかりすぎて実用的ではありません。

プログラミング競技会は、単純な実装が許容できる時間内に実行できないという問題でいっぱいです。問題の核心は、一般的にはるかに明白ではありませんが、はるかに高速に実行される改良されたアルゴリズムを考え出すことです。

于 2009-08-24T20:20:50.830 に答える
2

時間をかけてあなたの質問をもう少し詳しく読んだところ、完璧な例がありました。

単純な実装が技術的には問題の機能的な解決策になる可能性があるが、実際にはまったく使用できないことを (理想的には、技術に詳しくない人にも) 説明する良い明確な例です。

ボゴソートをお試しください！

カードのデッキを並べ替えるためにボゴソートが使用された場合、それはデッキが正しいかどうかをチェックすることで構成され、そうでない場合はデッキを空中に投げ、ランダムにカードを拾い上げ、プロセスを繰り返します。デッキが決まるまで。

于 2008-11-03T16:28:23.833 に答える
2

単純な実装は次のとおりです。

  • 直感的;
  • 最初に頭に浮かぶ;
  • 多くの場合、感染性および/またはバグのあるインコーナーケース。
于 2010-01-20T10:05:20.550 に答える
1

数が素数であるかどうかを判断する (素数テスト) は、優れた例です。

素朴な方法は、x = 2..square root(n) が少なくとも 1 つの x に対してゼロである n mod x かどうかをチェックするだけです。この方法は、素数が非常に大きい場合に非常に遅くなる可能性があり、暗号化で使用することはできません。

一方、確率的または高速な決定論的テストがいくつかあります。これらは複雑すぎてここで説明することはできませんが、詳細については、関連するウィキペディアの記事を参照してください: http://en.wikipedia.org/wiki/Primality_test

于 2008-11-02T20:49:30.170 に答える
1

誰かがデータベースから 1 つのフィールドを抽出する方法を理解し、PHP またはページの各フィールドに対してデータベースに個別のクエリを実行する任意の言語で Web ページを作成するとします。動作しますが、信じられないほど遅く、非効率的で、保守が困難です。

于 2008-11-02T20:51:16.297 に答える
1

ナイーブとは、悪いとか使い物にならないという意味ではなく、特定の状況や特定の目的で問題を引き起こす特定の性質を持つことを意味します。

もちろん、古典的な例はソートです。10 個の数値のリストをソートするというコンテキストでは、古いアルゴリズム (pogo ソートを除く) はどれもうまく機能します。ただし、数千以上の規模になると、通常、選択ソートは O(n^2) 時間の品質を持ち、目的には遅すぎるため、単純なアルゴリズムであると言います。非ナイーブ アルゴリズムは、O(n lg n) 時間の品質を持ち、目的に十分な速さであるため、クイックソートです。

実際、10 個の数字のリストをソートするコンテキストでは、選択ソートよりも時間がかかるため、クイックソートは単純なアルゴリズムであるというケースが考えられます。

于 2008-11-02T20:59:30.573 に答える
0

（本当に素朴な実装がまだ投稿されているのを見たことがないので...）

次の実装は、エッジケースをカバーしておらず、他のケースでは機能しないため、「ナイーブ」です。理解するのは非常に簡単で、プログラミングメッセージを伝えることができます。

   def naive_inverse(x):
        return 1/x

そうなる：

  • x=0でブレーク
  • 整数を渡されたときに悪い仕事をする

これらの機能を追加することで、より「成熟した」ものにすることができます。

于 2008-11-02T21:59:52.447 に答える
0

カードのデッキをソートするために通常使用する直感的なアルゴリズム (挿入ソートまたは選択ソート、両方とも O(n^2)) は、学習と実装が容易であるため、ナイーブと見なすことができますが、デッキのデッキにはうまく拡張できません。 、たとえば、100000枚のカード:D。一般的な設定では、リストをソートするより高速な (O(n log n)) 方法があります。

ただし、ナイーブが必ずしも悪いことを意味するわけではないことに注意してください。挿入ソートが適切な選択となる状況があります (たとえば、すでにソート済みの大きなデッキがあり、追加する未ソートのカードがいくつかある場合)。

于 2008-11-02T21:13:31.293 に答える
0

100,000,000 エントリ以上のバブル ソート。

于 2008-11-02T20:48:27.223 に答える
-5

AO(n!) アルゴリズム。

foreach(object o in set1)
{
    foreach(object p in set1)
    {
        // codez
    }
}

これは、小さなセットではうまく機能しますが、大きなセットでは指数関数的に悪化します。

もう 1 つは、スレッド化を考慮しない単純なシングルトンである可能性があります。

public static SomeObject Instance
{
     get
     {
          if(obj == null)
          {
               obj = new SomeObject();
          }

          return obj;
     }
}

2 つのスレッドが同時にアクセスすると、2 つの異なるバージョンを取得する可能性があります。深刻な奇妙なバグにつながります。

于 2008-11-02T20:48:53.900 に答える