5

最近の技術面接で、教科書に出てくる頻度の高い単語（出現回数が最大の単語）を見つけるプログラムを書いてほしいと頼まれました。プログラムは、最小限のメモリで教科書全体を処理するように設計する必要があります。パフォーマンスは問題ではありません。単語の頻度を見つけるプログラムを作成することはできましたが、多くのメモリを消費しました。

この操作のメモリ負荷を軽減するにはどうすればよいですか? 戦略/解決策はありますか?

-スネハル

4

12 に答える 12

4

私はおそらくこれに反対票を投じるでしょう...

テキストが英語で、最も頻繁に使用される上位5つの単語を検索したい場合は、次のプログラムを使用してください。

print "1. the\n";
print "2. of\n";
print "3. and\n";
print "4. a\n";
print "5. to\n";

高速で実行され、最小限のメモリを消費します！

于 2009-04-12T19:06:06.723 に答える
3

パフォーマンスが本当に問題にならない場合は、各単語を順番に調べて、「上位 N」にあるかどうかを確認し、そうでない場合は、出現するすべての単語を数えます。このようにして、N 値のみを保存します。もちろん、同じ単語を何度も数えることになりますが、あなたが言ったように、パフォーマンスは問題ではなく、コードは自明です (一般的に望ましいことです - 他のすべてが等しい場合)。

于 2009-04-12T18:10:32.707 に答える
2

多くの優れた面接の質問と同様に、質問は少し曖昧/不正確に表現され、面接対象者に明確な質問と状態の仮定を尋ねるように強制します。ここにある他の多くの答えは良いと思います。それらはこれらの仮定を突いて、全体像の理解を示しているからです。

テキストはどこかに「オフライン」で保存されていると思いますが、テキスト全体をメモリにロードせずに、テキスト内の各単語を反復処理する方法があります。

次に、以下のF＃コードで上位N個の単語を検索します。データ構造はキーと値のペア（単語、頻度）のマッピングであり、それらの上位Nのみを保持するため、メモリ使用量はO（N）と小さくなります。実行時間はO（numWordsInText ^ 2）です。これは貧弱ですが、問題の制約を考えると許容できます。アルゴリズムの要点は単純です。テキスト内の単語ごとに、それが発生する回数を数え、それが実行中のベストNにある場合は、それをリストに追加して、前の最小エントリを削除します。

以下の実際のプログラムは、説明の便宜のために、テキスト全体をメモリにロードすることに注意してください。

#light
// some boilerplate to grab a big piece of text off the web for testing
open System.IO 
open System.Net 
let HttpGet (url: string) = 
    let req = System.Net.WebRequest.Create(url) 
    let resp = req.GetResponse() 
    let stream = resp.GetResponseStream() 
    let reader = new StreamReader(stream) 
    let data = reader.ReadToEnd() 
    resp.Close() 
    data 
let text = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let words = text.Split([|' ';'\r';'\n'|], System.StringSplitOptions.RemoveEmptyEntries)
// perhaps 'words' isn't actually stored in memory, but so long as we can 
// 'foreach' over all the words in the text we're good
let N = 5  // how many 'top frequency' words we want to find
let FindMin map =
    // key-value pair with mininum value in a map
    let (Some(seed)) = Map.first (fun k v -> Some(k,v)) map
    map |> Map.fold_left 
        (fun (mk,mv) k v -> if v > mv then (mk,mv) else (k,v)) 
        seed
let Main() =
    let mutable freqCounts = Map.of_list [ ("",0) ]
    for word in words do
        let mutable count = 0
        for x in words do
            if x = word then
                count <- count + 1
        let minStr,minCount = FindMin freqCounts
        if count >= minCount then
            freqCounts <- Map.add word count freqCounts
        if Seq.length freqCounts > N then
            freqCounts <- Map.remove minStr freqCounts
    freqCounts 
    |> Seq.sort_by (fun (KeyValue(k,v)) -> -v) 
    |> Seq.iter (printfn "%A")
Main()

出力：

[the, 75]
[to, 41]
[in, 34]
[a, 32]
[of, 29]
于 2009-04-12T19:06:17.723 に答える
2

1 つの方法は、最初にリストをソートすることです。

多くのメモリを必要とせずに単語をその場で並べ替えることができます (パフォーマンスが低下します)。

そして、並べ替えられた形式であるため、すべてをメモリに保存する必要なく、最大頻度の単語を見つける単純なカウント ループを作成できます。

于 2009-04-12T18:07:35.413 に答える
2

プロセスメモリが多いということですか？もしそうなら、1 つの方法は、ディスクを仮想メモリとして使用することです (別名、ファイルシステム ラッパーを記述します)。

于 2009-04-12T18:07:42.480 に答える
0

まあ、絶対にひどいパフォーマンスが必要な場合は...

本の最初の単語を取り、それが何回出現するかを数えます。本の 2 番目の単語を取り、それが何回出現するかを数えます。最後の単語より多い場合は、最後の単語を破棄します。などなど...どこかにリストを保持しない限り、同じ単語を複数回カウントすることになりますが、本当にメモリを最小限に抑えたい場合は、数個の int しか必要ありません。O(n^2) 時間で実行する必要があります。ここで、n は本の単語数です。

于 2009-04-12T19:16:17.043 に答える
0

単語キーのバイナリ ツリーを作成するのはどうですか (ファイルから単語を読み続けながら)。これは、O(Log(n)) で既に繰り返されている単語を検索するのに役立ちます。最後に、トップワード検索で O(nLog(n)) を取得します。

基本的なアルゴリズムは

ファイル内の各単語について:

  1. 指定された単語の一意のキーを作成します (重み付けされた ascii char など、「bat」は 1*'b' + 2*'a' + 3*'c' のようになります。
  2. この単語をツリーに追加します。単語が既に存在する場合は、新しいカウントを増やします。
  3. 単語と現在のカウントを供給して、maintainTop5(word, count) に入力します。maintainTop5() は、上位 5 カウントと関連する単語の動的リストを維持します。

ファイルの終わりには、上位 5 つの単語があります。

于 2012-02-09T07:40:30.513 に答える