Pythonのソート効率に関する質問

Question

申し訳ありませんので、私はコマンドラインベースのウェブサイト検索機能の実装を行っています。このウェブサイトには、アルファベット順に必要なすべてのリンクのリストがあります。

使い方だから、手紙B. 私の質問に関連したWebページに移動します

./find.py LinkThatStartsWithB 

ようなものになるだろうが何であるかをユーザの入力を使用してナビゲートするための最も効率的な/賢い方法ですウェブページに私が最初に考えていた何

は、リストを使用して、その後、単語の最初の文字を取得し、どこリストインデックスに行くする伝えるために数値識別子を使用しての線に沿って何かでした。

（A = 1、B = 2 ...） 例コード：

#Use base url as starting point then add extension on end. 
Base_URL = "http://www.website.com/" 

#Use list index as representation of letter 
Alphabetic_Urls = [ 
     "/extensionA.html", 
     "/extensionB.html", 
     "/extensionC.html", 
     ] 

または辞書であろうが、より良い賭けでありますか？

ありがとう

Answer 1

はどのようにURLのリストを得ていますか？あなたのコマンドラインアプリがリンクのためのウェブサイトをクロールして、あなただけの辞書を構築し、単一のアイテムを探している場合

は無意味です。それはあなたが行くようにちょうど確認するだろうようにdictを構築するために少なくとも長いがかかります！例えば、同じように検索：あなたは（というだけで、単一のコマンドラインパラメータよりも）、複数の検索を行うことが予定されている場合は、それはのようなものを使用して辞書を構築する価値があるかもしれない、

for link in mysite.getallLinks(): 
    if link[0] == firstletter: 
     print link 

を：

import collections 
d=collections.defaultdict(list) 
for link in mysite.getallLinks(): 
    d[link[0]].append(link)    # Dict of first letter -> list of links 

# Print all links starting with firstletter 
for link in d[firstletter]: 
    print link 

ちょうど26バケットがあることを与えられたが、違いの多くを作ることはないだろう。

Answer 2

辞書！ O（1）

Answer 3

ここにコード読み取りが最も簡単になるものは何でも賢いやり方になります。あなたはリストに26個のアイテムしか持っていないとき、それを調べるためにどんなアルゴリズムを気にしますか？あなたは実際に何かを使用しなければならないでしょう、実際には愚かなことがパフォーマンスに影響を与えるようにする。

あなたがが性能に本当に興味があるなら、あなたはベンチマークさまざまなオプションに必要があると思います。複雑さを見るだけでは、関連する要因が隠されているため、全体の話は分かりません。たとえば、辞書検索では、キーのハッシュを計算し、テーブル内でそれを調べ、次に等価性をチェックします。短いリストの場合、ハッシュアルゴリズムがどれほどコストがかかるかによって、単純な線形検索がより効率的になることがあります。あなたの例ではしかし、本当に正確であれば、あなただけの

入力文字列の最初の文字を取り、そこからURLを予測することはできませんか？あなたが持っている（と常に持つことになります）場合（"/extension" + letter + ".html"）

Answer 4

辞書は、アイテムの数が少ない選ぶとよいでしょう。 URLのリストが将来拡張される予定の場合、実際にはURLを文字でソートし、それぞれの辞書をハードコーディングするのではなく入力と照合したいと思うでしょう。

Answer 5

合計26項目しか話していないように思えるので、おそらく効率についてあまり心配する必要はありません。あなたが思いつくものは、すばやくすべきです。

一般的に、問題のドメインに最も近いデータ構造を使用することをお勧めします。たとえば、文字をURLにマップしようとしているように見えます。たとえば、これが「A」URLで、これが「B」URLです。その場合には、辞書のようなマッピング・データ構造が適切に聞こえる：

html_files = { 
    'a': '/extensionA.html', 
    'b': '/extensionB.html', 
    'c': '/extensionC.html', 
} 

この正確な例では、あなたが実際にそれをごまかすし、完全なデータ構造をスキップすることもできますが - '/extension%s.html' % letter.upper() :)