Bir liste tarama

Question

Python'da bir listeyi taramam gerekiyor. Ben dosyadan yüklemek açabiliyorum ve basit operasyon yapmak, ama şunları yapmaya çalıştığım:

L = [1,2,3,4,5,6,7,8] 

birinci elemanın başlayarak aşağıdaki çıktıyı üretmek istiyorum:

1 
    2,3,4,5,6,7,8 
    3,4,5,6,7,8 
    4,5,6,7,8 
    5,6,7,8 
    6,7,8 
    7,8 
    8 
2 
    3,4,5,6,7,8 
    4,5,6,7,8 
    5,6,7,8 
    6,7,8 
    7,8 
    8 
3 
    4,5,6,7,8 
    5,6,7,8 
    6,7,8 
    7,8 
    8 
4 
    5,6,7,8 
    6,7,8 
    7,8 
    8 

ve bunun gibi.

Böyle bir şey çalışıyordu: Beni

fo = open(sys.argv[1], 'r') 
L = fo.readlines() 
for i in range(len(L)): 
    print str(L[i]) 
    for j in range(len(L)-1-i): 
     print '...' + str(L[i+j+1]) 

yardımcı olabilir mi?

Answer 1

Bu nasıl? Güzel ve basit okumak için: Liste temp boş değilken

---

while temp

>>> for i, j in enumerate(L): 
...  print L[i] 
...  temp = map(str, L[j:]) 
...  while temp: 
...    print ' ', ','.join(temp) 
...    temp = temp[1:] 
... 
1 
    2,3,4,5,6,7,8 
    3,4,5,6,7,8 
    4,5,6,7,8 
    5,6,7,8 
    6,7,8 
    7,8 
    8 
2 
    3,4,5,6,7,8 
    4,5,6,7,8 
    5,6,7,8 
    6,7,8 
    7,8 
    8 
3 
    4,5,6,7,8 
    5,6,7,8 
    6,7,8 
    7,8 
    8 
... 

anlamına gelir. Liste

---

Bir başka not tamsayılar dolu (ve böylece str.join yöntem işe yaramaz) olduğu için biz burada map(str, L[j:]) aramak zorunda dosyalarla çalışırken, bir with deyimini kullanmak daha pythonic var:

with open(sys.argv[1], 'r') as fo: 
    L = fo.readlines() 

Answer 2

Haidro yanıtı istenen çıktıyı üretirken, bunun sağlanan görevi yapmak için oldukça verimsiz bir algoritma olduğunu söylemeliyim.

hızlı analizi:

for i, j in enumerate(L):   # loop number 1, for i from 1 to N 
    print L[i] 
    temp = map(str, L[j:])   
    while temp:     # nested loop number 2, for j from i to N 
     print ' ', ','.join(temp) # nested loop number 3, for k from j to N 
     temp = temp[1:] 

böyle basit bir görev için çok fazla iş var. Bunu sadece bir kez ve daha sonra dize katılmadan, çok simplier ve daha hızlı yapılabilir düşünüyorum baskı altdizgelerin (DCM, yorum olarak bahsedilen biz dizede elemanların konumlarını ön hesaplama gerektiğini keyfi sayıları yazdırmak için muktedir gibi):

s = ",".join(map(str, l))     # creating string 
p = [len(str(x)) + 1 for x in l]   # calculating length of each element 
p = [sum(p[:i]) for i in range(len(p))] # calculating positions with rolling total 
for i in range(len(l)):     # loop number 1 
    print l[i] 
    for j in range(i + 1, len(l)):   # nested loop number 2 
     print ' ', s[p[j]:] 

İşte yürütme sürelerinin hızlı bir profili (Haol koduyla worker1 ve madeni ile worker2 işlevi oluşturuyorum).

>>> from timeit import timeit 

>>> timeit("worker1(l)", "from testSO import worker1, l", number=10) 
0.0016222212978796024 
>>> timeit("worker1(l*10)", "from testSO import worker1, l", number=10) 
0.33153371422580324 
>>> timeit("worker1(l*100)", "from testSO import worker1, l", number=10) 
163.25908817145972 

O O(N^3)

>>> timeit("worker2(l)", "from testSO import worker2, l", number=10) 
0.0006974355000011201 
>>> timeit("worker2(l*10)", "from testSO import worker2, l", number=10) 
0.03448374103493279 
>>> timeit("worker2(l*100)", "from testSO import worker2, l", number=10) 
4.446190059150922 

gibi büyür O değil

O(N^2) benzese büyür Ben orijinal olduğunu düşünüyorum: Eğer giriş uzunluğu N artırmak yürütme zamanı nasıl büyür görebilirsiniz soru, performans kritik görevine benziyor, ama sanırım insanlar algoritmanın neden beklediğinden daha yavaş olabileceğini görüyorsa iyi olur.