3

エントリ値がキーによって別のエントリを参照でき、最終的に現在の値のエントリがない場合、または「-」が検出された場合に終了する辞書があります。このデータ構造の目的は、各エントリの親を見つけ、「-」を「なし」に変換することです。たとえば、次のようにします。

d = {'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
  • 「1」は「-」にマップされるルートであるため、結果は「なし」になります。
  • 「0」の親は「6」で、親は「9」なので、結果は「9」になります。
  • 「3」には「1」の親があり、これは「-」にマップされるため、結果は「なし」になります。
  • 「2」には「3」の親があり、「1」の親は「-」にマップされるため、結果は「なし」になります。
  • 「4」は「5」の親のままにする必要があります
  • 「6」は「9」の親のままにする必要があります

私の冗長な解決策は次のとおりです。

d = {'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
print(d)
for dis, rep in d.items():
    if rep == "-":
        d[dis] = None
        continue

    while rep in d:
        rep = d[rep]
        if rep == "-":
            d[dis] = None
            break
    else:
        d[dis] = rep
print(d)

出力は次のとおりです。

{'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
{'1': None, '0': '9', '3': None, '2': None, '4': '5', '6': '9'}

結果は正しいです。「1」要素には親がなく、「2」/「3」要素は「1」を指します。また、親がいないはずです。

Python 3+を使用してこれを達成するためのより簡潔なPythonの方法はありますか？

4

3 に答える 3

4

辞書を「ウォーク」するには、次のようになるまでループでルックアップを実行します。

>>> def walk(d, val):
        while val in d:
            val = d[val]
        return None if val == '-' else val

>>> d = {'1': '-', '0': '6', '3': '1', '2': '3', '4': '5', '6': '9'}
>>> print {k: walk(d, k) for k in d}
{'1': None, '0': '9', '3': None, '2': None, '4': '5', '6': '9'}
于 2012-04-19T02:55:26.753 に答える
1

このような関数を定義できます

def recursive_get(d, k):
    v = d[k]
    if v == '-':
        v = d[k] = None
    elif v in d:
        v = d[k] = recursive_get(d, v)
    return v

キーにアクセスするために使用recursive_getすると、トラバースするときに値が変更されます。これは、必要のないブランチを梱包する時間を無駄にしないことを意味します

>>> d = {'1': '-', '3': '1', '2': '3'}
>>> recursive_get(d, '3')
>>> d
{'1': None, '3': None, '2': '3'}         # didn't need to visit '2'

>>> d = {'1': '-', '3': '1', '2': '3'}
>>> recursive_get(d, '2')
>>> d
{'1': None, '3': None, '2': None}

d強制的に最終状態にしたい場合は、すべてのキーをループするだけです。

for k in d:
    recursive_get(d, k)
于 2012-04-19T02:28:31.843 に答える
1

これまでの3つのアプローチに関するプロファイリング統計を投稿したいと思います。

Running original procedural solution.
5 function calls in 0.221 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.000    0.000    0.221    0.221 <string>:1(<module>)
    1    0.221    0.221    0.221    0.221 test.py:12(verbose)
    1    0.000    0.000    0.221    0.221 {built-in method exec}
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    1    0.000    0.000    0.000    0.000 {method 'items' of 'dict' objects}

885213
Running recursive solution.
     994022 function calls in 1.252 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.000    0.000    1.252    1.252 <string>:1(<module>)
994018    0.632    0.000    0.632    0.000 test.py:27(recursive)
    1    0.620    0.620    1.252    1.252 test.py:35(do_recursive)
    1    0.000    0.000    1.252    1.252 {built-in method exec}
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

885213
Running dict comprehension solution.
     994023 function calls in 1.665 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.059    0.059    1.665    1.665 <string>:1(<module>)
994018    0.683    0.000    0.683    0.000 test.py:40(walk)
    1    0.000    0.000    1.606    1.606 test.py:45(dict_comprehension)
    1    0.923    0.923    1.606    1.606 test.py:46(<dictcomp>)
    1    0.000    0.000    1.665    1.665 {built-in method exec}
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

885213

以下は、3つのアプローチを実行するためのコードです。

import cProfile
import csv
import gzip

def gzip_to_text(gzip_file, encoding="ascii"):
    with gzip.open(gzip_file) as gzf:
        for line in gzf:
            yield str(line, encoding)

def verbose(d):
    for dis, rep in d.items():
        if rep == "-":
            d[dis] = None
            continue

        while rep in d:
            rep = d[rep]
            if rep == "-":
                d[dis] = None
                break
        else:
            d[dis] = rep
    return d

def recursive(d, k):
    v = d[k]
    if v == '-':
        v = d[k] = None
    elif v in d:
        v = d[k] = recursive(d, v)
    return v

def do_recursive(d):
    for k in d:
        recursive(d, k)
    return d

def walk(d, val):
    while val in d:
        val = d[val]
    return None if val == '-' else val

def dict_comprehension(d):
    return {k : walk(d, k) for k in d}

# public dataset pulled from url: ftp://ftp.ncbi.nih.gov/gene/DATA/gene_history.gz
csvr = csv.reader(gzip_to_text("gene_history.gz"), delimiter="\t", quotechar="\"")
d = {rec[2].strip() : rec[1].strip() for rec in csvr if csvr.line_num > 1}
print("Running original procedural solution.")
cProfile.run('d = verbose(d)')
c = 0
for k, v in d.items():
    c += (1 if v is None else 0)
print(c)
print("Running recursive solution.")
cProfile.run('d = do_recursive(d)')
c = 0
for k, v in d.items():
    c += (1 if v is None else 0)
print(c)
print("Running dict comprehension solution.")
cProfile.run('d = dict_comprehension(d)')
c = 0
for k, v in d.items():
    c += (1 if v is None else 0)
print(c)
于 2012-04-19T17:56:43.927 に答える