Ro'yxatda python ro'yxatini tuzish

Men katta ro'yxatda aniq tartibda elementlarni necha marta hisoblashni istayman. Masalan, agar menda [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5 ] va [1,2,3] bir-biri bilan qanchalik ko'p ekanligini bilmoqchi edim (javob bu holda 4 ).

Men "3" raqamini tekshirishni rejalashtirdim (shu sababli hozirda [2,7,12,17] ) ni qaytarib beraman. ro'yxatga kirib, oldida ikkita pozitsiyani tekshiring, agar ular "1" va "2" ga mos keladigan bo'lsalar, 1-raqamga qo'shib, qarashni davom eting. echim?

2
Bir-biriga o'xshash o'yinlarni hisoblashingiz kerakmi? Masalan, [1, 1, 1] ichida [1, 1] necha marta bor?
qo'shib qo'ydi muallif vaultah, manba
Yo'q, mening vaziyatimda bir-biriga o'xshamaydigan o'yinlar yo'q.
qo'shib qo'ydi muallif Banana, manba

6 javoblar

Bu erda har qanday o'lchamdagi va har qanday element elementlari uchun ishlaydigan umumiy yechim mavjud. Bundan tashqari, juda ko'p joylarda samarali bo'ladi, chunki u faqat yineleyicilarda ishlaydi.

from itertools import islice

def count(lst, seq):
    it = zip(*(islice(lst, i, None) for i in range(len(seq))))
    seq = tuple(seq)
    return sum(x == seq for x in it)
In [4]: count(l, (1, 2, 3))
Out[4]: 4

Idea lst bo'yicha len (seq) bo'ylab surilgan bir oyna oynasini yaratish va tuple (seq) . Bu shuni anglatadiki, count bir-biriga mos keladigan ma`lumotlarni hisobga oladi:

In [5]: count('aaa', 'aa')
Out[5]: 2
5
qo'shib qo'ydi
O'Rning ro'yxati ~ 6 million elementlarga ega bo'lgani uchun, islice ni ishlatish yaxshi bo'ladi.
qo'shib qo'ydi muallif Aran-Fey, manba
@Rawing: Ha, rozilik berdim.
qo'shib qo'ydi muallif vaultah, manba

Ints ro'yxatlari uchun siz strings ga aylantirilib, keyin hisoblash usulidan foydalanasiz:

>>> x = [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]
>>> y = [1,2,3]
>>> s = ',' + ','.join(str(i) for i in x) + ','
>>> t = ',' + ','.join(str(i) for i in y) + ','
>>> s.count(t)
4

Ro'yxatdagi elementlar vergulni o'z ichiga olgan satrlari bo'lsa, bu usul muvaffaqiyatsiz bo'lishi mumkin (@schwobaseggl sharhlarda ishora qiladi). Hech qaysi satrda bo'lmasligi ma'lum bo'lgan chegarachi tanlashingiz kerak yoki count usuliga kamaytirmaydigan butunlay boshqa usulni qo'llashingiz kerak.

On Edit: I added a fix suggested by @Rawing to address a bug pointed out by @tobias_k . This turns out to be a more subtle problem than it first seems.

2
qo'shib qo'ydi
@schwobaseggl '12, 3 '! =' 1,23 ' Tekshirgichni ishlatish nuqtasi noyob okunabilirliği himoya qilish (hech bo'lmasa int ro'yxatlari uchun).
qo'shib qo'ydi muallif John Coleman, manba
@Banana Siz buni amalga oshirishingiz kerak edi, lekin count juda tez usul.
qo'shib qo'ydi muallif John Coleman, manba
@schwobaseggl Men o'z qarorimni o'zboshimchalik bilan pastki ro'yxatlarni ro'yxatga olishning umumiy usuli bo'lgan usul deb da'vo qilmadim. Ko'p hollarda, shu jumladan, masalaning misolini qamrab oladigan juda yaxshi, tez va iflos yondashuv. Shunday bo'lsa-da, siz yaxshi fikrni oshirasiz. Ichaklar ro'yxatlari holatida cheklovni tanlash bilan muomala qilish kerak.
qo'shib qo'ydi muallif John Coleman, manba
@tobias_k Yaxshi nuqta. Bu shafqatsiz e'tirozdir. Men o'chirib tashlayman - Agar OP javobni tan olmasa (bu holda men uni o'chirib tashlamasligim ajablanarli emas).
qo'shib qo'ydi muallif John Coleman, manba
Yaxshi saqlanish. Rahmat.
qo'shib qo'ydi muallif John Coleman, manba
Bu [12, 3] va [1, 23] ni bir xil narsaga aylantiradi.
qo'shib qo'ydi muallif schwobaseggl, manba
Bu butun sonlar uchun. Shunga qaramasdan, asoschi boshqa turdagi ma'lumotlarga ega: ['1,2', '3' va ['1', '2,3'
qo'shib qo'ydi muallif schwobaseggl, manba
@JohnColeman Albatta, bu o'limga olib keluvchi e'tiroz emas. Faqat ikkala satrning boshida va oxirida vergulni qo'yishingiz kerak.
qo'shib qo'ydi muallif Aran-Fey, manba
Hatto int ro'yxatlarini uchun esa, bu qidirish naqshlari 1,2,3 bo'lsa va ro'yxatda, masalan, 11,2,33 .
qo'shib qo'ydi muallif tobias_k, manba
Katta ro'yxatga olish uchun xarita() ni barcha bu tamsayılarni satrlarga aylantirishda samaraliroq bo'ladimi?
qo'shib qo'ydi muallif reticentroot, manba
Mening ro'yxatimda ~ 6 million element bo'lsa, u oddiy vaqtda ishlaydi?
qo'shib qo'ydi muallif Banana, manba
x = [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]
y = [1,2,3]

count = 0
for i in range(len(x)-len(y)):
    if x[i:i+len(y)] == y:
        count += 1
print(count)
1
qo'shib qo'ydi

Ro'yxatni yineleyebilir va pastki ro'yxatlarni solishtirishingiz mumkin:

In [1]: lst = [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]
In [2]: sub = [1,2,3]
In [3]: [i for i, _ in enumerate(lst) if lst[i:i+len(sub)] == sub]
Out[3]: [0, 5, 10, 15]

Shunga qaramasdan, juda katta ro'yxat va kichik ro'yxatda ushbu ro'yxat juda taqiqlangan, chunki u sub ro'yxatiga solishtirish uchun asl ro'yxatning juda ko'p qismini yaratadi. Biroz uzoqroq bo'lgan versiyada, ro'yxatning tegishli pozitsiyalarining har birini pastki ro'yxatlar bilan taqqoslash uchun all dan foydalanishingiz mumkin:

In [5]: [i for i, _ in enumerate(lst) if all(lst[i+k] == e for k, e in enumerate(sub))]
Out[5]: [0, 5, 10, 15]
0
qo'shib qo'ydi

Bu ketma-ketlikning qaytarib berilishigacha bo'sh ro'yxat mavjud bo'lgunga qadar har doim takrorlanadigan eng uzoq davom etadigan umumiy muammo.

O'ylaymanki, bu holatda samarali algoritm uchun eng yaxshi narsa O (n * m) dir, bu erda n - katta ro'yxatdagi elementlarning soni va m - kichik ro'yxatdagi elementlarning soni. Siz, albatta, katta ketma-ketlikdan kichik tartibni olib tashlash va jarayonni takrorlashning qo'shimcha qadamiga ega bo'lishingiz kerak.

Mana algoritm:

  1. lcs toping (bigList, smallList)
  2. BigList birinchi ro'yxatini kichik ro'yxatidan chiqaring
  3. lcs bo'sh ro'yxatga kelguniga qadar takrorlang.
  4. Yineleme sonini qaytaring

Pythonda yozgan lcs dasturining bajarilishi:

def lcs(first, second):
    results = dict()
    return lcs_mem(first, second, results)

def lcs_mem(first, second, results):
    key = ""
    if first > second:
        key = first + "," + second
    else:
        key = second + "," + first

    if len(first) == 0 or len(second) == 0:
        return ''
    elif key in results:
        return results[key]
    elif first[-1] == second[-1]:
        result = lcs(first[:-1], second[:-1]) + first[-1]
        results[key] = result
        return result
    else:
        lcsLeft = lcs(first[:-1], second)
        lcsRight = lcs(first, second[:-1])

        if len(lcsLeft) > len(lcsRight):
            return lcsLeft
        else:
            return lcsRight

def main():
    pass


if __name__ == '__main__':
    main()

Yuqoridagi algoritmga o'zgartirish kiritishga harakat qiling.

0
qo'shib qo'ydi

Qarorning samaradorligini murakkablikdan aniqlash mumkin. Google'da algoritmning murakkabligi haqida ko'proq ma'lumot oling.

Va sizning holatlaringizda murakkablik 2n dir, bu erda n - elementlarning soni.

Bu erda n murakkabligi bilan yechim, bu ro'yxatni faqat bir marta, ya'ni n sonini bir marta bosib o'tadi.

def IsSameError(x,y):
    if (len(x) != len(y)):
        return False

    i = 0
    while (i < len(y)):
        if(x[i] != y[i]):
            return False
        i += 1

    return True

x = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
y = [1, 2, 3]

xLength = len(x)
yLength = len(y)
cnt = 0
answer = []
while (cnt+3 < xLength):
    if(IsSameError([x[cnt], x[cnt+1], x[cnt+2]], y)):
        answer.append(x[cnt])
        answer.append(x[cnt+1])
        answer.append(x[cnt + 2])
        cnt = cnt + 3
    else:
        cnt = cnt + 1


print answer
0
qo'shib qo'ydi
Bu murakkabligi ancha past bo'lishi mumkin, lekin uni stolsiz belgilash yaxshiroq deb aytish qiyin. Mening fikrimcha, Pythonda looplar uchun c darajasida tezlikda ishlaydi, ikkinchisida looplar yo'q. Boshqacha aytganda Python for loop bilan loop qilish tezroq. Xuddi shu tarzda siz o'zingizning appendlaringiz bilan xotira ajratishni yaratasiz, bu esa og'ir jarayondir. Shu sababli murakkablikdagi savdo ushbu stsenariyda bunga loyiq bo'lmasligi mumkin.
qo'shib qo'ydi muallif reticentroot, manba
Men loop va loop o'rtasida farqni bilmayman. Iltimos, nima uchun asta-sekinlik bilan sababini bering. Javobni boshqa javob bilan taqqoslasangiz, ilova qismini atlayabilir va loop uchun loop bilan almashtirishimiz mumkin. Ammo ha juda katta bilim.
qo'shib qo'ydi muallif Ujjaval Moradiya, manba
Python
Python
372 ishtirokchilar

Bu guruh python dasturlash tilini muhokama qilish uchun. Iltimos, o'zingizni hurmat qiling va faqat dasturlash bo'yicha yozing. Botlar mavzusini @botlarhaqida guruhida muhokama qling! FAQ: @PyFAQ Offtopic: @python_uz_offtopic

Python offtopic group !
Python offtopic group !
150 ishtirokchilar

@python_uz gruppasining offtop gruppasi. offtop bo'lsa ham reklama mumkin emas ) Boshqa dasturlash tiliga oid gruppalar @languages_programming