0

さまざまな並べ替えアルゴリズムを使用して、あらゆる種類のデータ型を並べ替える必要がある学校のプロジェクトがあります。基数ソートはうまく機能しますが、整数以外はソートできません。すべてのデータ型が整数としてソートされるため、おそらく整数以外のソート結果を追加するつもりはありません。

そうは言っても、文字列を整数に変換するより良い方法があるかどうか知りたいですか? これが私が持ってきたものです。私はpythonの裏をかきたくないので、標準関数をできるだけ使用しようとしました。

def charToHex(char):
    return hex(ord(char))[2:]

def stringToHex(text):
    t = ''
    for char in text:
        t += charToHex(char)

    return t

def stringToInt(text):
    return int(stringToHex(text), 16)

print stringToInt('allo')
print stringToInt('allp')
print stringToInt('all')

それはうまく機能しますが、それを処理するより良い方法があるかどうかを知りたいです。基数ソートで整数以外のものをソートすることは無意味に聞こえます。整数のリストをソートできたとしても。すべてのキーの値をリストに戻す必要があります。

みたいなことをしようと思っていました。リストの各値について、整数キーを取得します。そのキーをハッシュテーブル内に置き、値をそのハッシュテーブルのリストに入れます。リスト内の値を整数キーに置き換えてから、キーのリストを並べ替えます。

ソートされたリスト内の各キーについて、そのキーの値のリストを取得し、1 つの項目をポップします。その項目をリストに入れて続行します。

また、変換を必要としない他の並べ替えの代わりに基数並べ替えを使用して、このプロセスを最適化する方法があるかどうかも知りたいです。リスト内の項目の量が 50000 を超える場合があります。

編集

実際、ここのコードは異なるサイズの文字列では機能しません。それを確認する方法がよくわかりません。文字列にスペースを埋め込むとうまくいくようです。

def getMaxLen(ls):
    lenght = 0

    for text in ls:
        lenght = max(lenght, len(text))

    return lenght

def convertList(ls):
    size = getMaxLen(ls)
    copy = ls[:]

    for i, val in enumerate(copy):
        copy[i] = stringToInt(val.ljust(size, ' '))

    return copy

print convertList(["allo", "all", "bal"])
4

1 に答える 1

2

まずはこちらの記事をご覧ください。その記事は、はい、場合によっては、他のどのソートよりも高速な文字列の基数ソート アルゴリズムを理解できることを示しています。

次に、さらに重要なこととして、時期尚早の最適化を行っていないか自問してください。sort()Python の関数を使用して 50k のアイテムを並べ替えると、信じられないほど高速になります。これがアプリケーションのボトルネックであると確信していない限り、私はそれについて心配せず、sort()関数を使用するだけです。それがボトルネックである場合は、これらすべての並べ替えを回避できる方法がないことも確認します (たとえば、キャッシュ、並べ替えられていないデータで動作するアルゴリズムなど)。

于 2013-05-06T13:33:32.047 に答える