Python-da, bir qator ichida ikki nusxadagi katalog o'chirish

Ikki nusxadagi bir nechta qatordan kam ishlaydigan narxga ega bo'lgan qatordan e'tiborsizlik qilmoqchiman. Misol uchun;

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

kutilgan natijalar kabi bo'lishi kerak

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

Arraylarni bir qatorda solishtirish mumkinmi? Men shunday yo'l tutyapman;

 A = [['1','2'],['3','4'],['5','6'],['1','2'],['3','4'],['7','8']]
        output = set()
        for x in A:
            output.add(x)
        print (output)

Biroq, bu talab qiladi;

TypeError: unhashable turi: "ro'yxat"

0
Siz ro'yxatni ro'yxatga qo'yishingiz mumkin emas, chunki ro'yxat tovlanuvchi emas. Va agar u ishlagan bo'lsa ham, siz buyurtma berishni yo'qotasiz.
qo'shib qo'ydi muallif Moses Koledoye, manba
Siz ro'yxatni ro'yxatga qo'yishingiz mumkin emas, chunki ro'yxat tovlanuvchi emas. Va agar u ishlagan bo'lsa ham, siz buyurtma berishni yo'qotasiz.
qo'shib qo'ydi muallif Moses Koledoye, manba
Bundan tashqari, ular ro'yxatlari arrays »emas
qo'shib qo'ydi muallif PM 2Ring, manba
Bundan tashqari, ular ro'yxatlari arrays »emas
qo'shib qo'ydi muallif PM 2Ring, manba
Bundan tashqari, ular ro'yxatlari arrays »emas
qo'shib qo'ydi muallif PM 2Ring, manba
@MosesKoledoye Buyurtma muhim emas, lekin xarajat muhim.
qo'shib qo'ydi muallif Awais, manba
@MosesKoledoye Buyurtma muhim emas, lekin xarajat muhim.
qo'shib qo'ydi muallif Awais, manba
@MosesKoledoye Buyurtma muhim emas, lekin xarajat muhim.
qo'shib qo'ydi muallif Awais, manba

7 javoblar

Qanday oddiy narsa haqida:

B = list(map(list, set(map(tuple, A))))

Mana mening "bakeoff" - iltimos sizning hal qilishingizni noto'g'ri talqin qilsam, menga xabar bering:

import timeit
from random import choice

DIGITS = list("123456789")

# one million elements in list
A = [[choice(DIGITS), choice(DIGITS)] for _ in range(1000000)]

def elena(A):  # MrName's solution is identical
    B = []

    for i in A:
        if i not in B:
            B.append(i)
    return B

def cdlane(A):

    return list(map(list, set(map(tuple, A))))

def VikashSingh(A):
    uniques = set()
    B = []

    for x in A:
        val = '-'.join([str(key) for key in x])
        if val not in uniques:
            B.append(x)
            uniques.add(val)
    return B

def AbhilekhSingh(A):
    def unique_elements(l):
        last = object()
        for item in l:
            if item == last:
                continue
            yield item
            last = item

    return list(unique_elements(sorted(A)))

# sanity check to make sure everyone one agrees on the answer
B = sorted(elena(A))
assert(B == sorted(cdlane(A)))
assert(B == sorted(VikashSingh(A)))
assert(B == sorted(AbhilekhSingh(A)))

print("elena:", format(timeit.timeit('B = elena(A)', number=10, globals=globals()), ".3"))

print("cdlane:", format(timeit.timeit('B = cdlane(A)', number=10, globals=globals()), ".3"))

print("VikashSingh:", format(timeit.timeit('B = VikashSingh(A)', number=10, globals=globals()), ".3"))

print("AbhilekhSingh:", format(timeit.timeit('B = AbhilekhSingh(A)', number=10, globals=globals()), ".3"))

Natijalar

elena: 17.5
cdlane: 2.04
VikashSingh: 10.0
AbhilekhSingh: 8.83
2
qo'shib qo'ydi
@Avays, sabrsizlik bilan nima? Boshqa echimlar Pythonda aylantirilsa, bu juda yaxshi bajarilishni ta'minlashi uchun C ga aylanadi. Va agar @VikashSingh '-' ni ishga tushirsa, unda x [] tugmachasini ([str (key) uchun kalitni kiritish uchun x]) qo'shsangiz, bu shunchaki (['1', '2' ) yanada samarali bo'lishi kerak. Shaxsan, men ko'pchilik nomzodlarning qaysi biri tez-tez potentsial ravishda noto'g'ri mehmonlarga aylanishini bilish uchun vaqtinchalik bakeoffni afzal ko'rmoqchiman ...
qo'shib qo'ydi muallif cdlane, manba
@sphericalcowboy, u o'z vazifasiga sharhlarida O'X tomonidan allaqachon murojaat qilgan.
qo'shib qo'ydi muallif cdlane, manba
Bu erda joylashgan barcha operatsiyalar O (n) ni tashkil etishdan boshqa narsa emas. Qatorlar hashtable-ga asoslanganligi sababli, set yaratilishi O (n) dir, chunki hashtable qidirish va kiritish O (1) dir. Bir to'siq uchun daraxt ishlatilgan bo'lsa, belgilangan tartibda yaratish jarayoni O (n log n) bo'lishi kerak. Amalda, hashtabel uchun barqaror (masalan, aralashgan to'qnashuvlar tufayli) yuqori daraxtning bir qismi n ga qadar tezroq bo'lishi uchun etarlicha yuqori bo'lishi mumkin.
qo'shib qo'ydi muallif 9000, manba
m * n * n bo'lishi mumkin deb o'ylayman. birinchi m * n dastlabki to'siqni yaratganimizda. Keyin order (n) bo'lishi kerak, shuning uchun m * n * n bo'lishi kerak.
qo'shib qo'ydi muallif Vikash Singh, manba
log (n) mumkin emas deb o'ylamayman. Chunki agar log (n) imkoni bo'lsa, uni qayta loyihalashtirishi va ro'yxatni tartiblash uchun ishlatishi mumkin. Biz biladigan kod log (n) bo'lishi mumkin emas.
qo'shib qo'ydi muallif Vikash Singh, manba
Buni tasavvur qiling, tasavvur qiling - bu [1,2,3] . Buning yagona noyob qadriyatlarga ega ekanligini bilish uchun O (n) eng yaxshisi.
qo'shib qo'ydi muallif Vikash Singh, manba
@cdlane vaqtni ko'raylik. Yaxshi o'rganish mumkin. :)
qo'shib qo'ydi muallif Vikash Singh, manba
@cdlane sizning yechimingiz yaxshiroq ishlaydigan ko'rinadi. Kattaroq ro'yxatlarni tekshirish endi.
qo'shib qo'ydi muallif Vikash Singh, manba
cdlane: Men ro'yxatda 1Million qiymatini tekshirdim. Sizning yechimingiz minalardan 3 barobar tezroq. @Awais: bu qadamlarning buyurtmasi sifatida siz bilan ahamiyatli emas.
qo'shib qo'ydi muallif Vikash Singh, manba
Biroq, bu ro'yxat elementlarining tartibini o'zgartirishi mumkin, ammo bu muammo yoki muammo bo'lmasligi mumkin.
qo'shib qo'ydi muallif Spherical Cowboy, manba
@cdlane: Qani endi! Qayta tiklash kerak edi, faqat uni hozir ko'rish.
qo'shib qo'ydi muallif Spherical Cowboy, manba
@VikashSingh Yaxshi.
qo'shib qo'ydi muallif Awais, manba
@VikashSingh Biz log (n) da buni qila olasizmi?
qo'shib qo'ydi muallif Awais, manba
@cdlane Ushbu kod satrining ishlaydigan narxi qanday?
qo'shib qo'ydi muallif Awais, manba
Ishlash xarajati nima?
qo'shib qo'ydi muallif Awais, manba
Xohlagan xarajatlarni ham eslatib o'ting.
qo'shib qo'ydi muallif Awais, manba

Siz ro'yxatni tartiblashtirishingiz va har bir elementni avvalgi bilan solishtirishingiz mumkin.

List length: n
Element length: m 
Complexity: Sorting(n * log(n) * m) + Comparison(n * m) = Total(n * log(n) * m)

Buni ko'ring:

def unique_elements(l):
    last = object()
    for item in l:
        if item == last:
            continue
        yield item
        last = item

def remove_duplicates(l):
    return list(unique_elements(sorted(l)))
1
qo'shib qo'ydi
Ishlash narxini qo'shib qo'ying va men bilan bog'laning.
qo'shib qo'ydi muallif Abhilekh Singh, manba
1Million ro'yxatdagi sizning yechimingiz CPU vaqtlarini beradi: foydalanuvchi 1,21 s, sys: 17,9 milodiy, jami: 1,23 s
qo'shib qo'ydi muallif Vikash Singh, manba
Xohlagan xarajatlarni ham eslatib o'ting. O'ylaymanki, u (n) bor. shundaymi?
qo'shib qo'ydi muallif Awais, manba
List length: n
Element length: m 
Complexity: 
    Iterate on n
    Format key by iterating on m
    Check key exists is set `uniques` in O(1)
    Total running time is is O(n * m)

Buning oddiy usuli:

uniques = set()
output = []
for x in A:
    val = '-'.join([str(key) for key in x])
    if val not in uniques:
        output.append(x)
        uniques.add(val)
print (output)

chiqdi:

[['1', '2'], ['3', '4'], ['5', '6'], ['7', '8']]
1
qo'shib qo'ydi
O (n) ishlash vaqti.
qo'shib qo'ydi muallif Vikash Singh, manba
Xohlagan xarajatlarni ham eslatib o'ting. O'ylaymanki, u (n) bor. shundaymi?
qo'shib qo'ydi muallif Awais, manba
List length: n
Element length: m 
Complexity: 
    Iterate on n
    Format key by iterating on m
    Check key exists is set `uniques` in O(1)
    Total running time is is O(n * m)

Buning oddiy usuli:

uniques = set()
output = []
for x in A:
    val = '-'.join([str(key) for key in x])
    if val not in uniques:
        output.append(x)
        uniques.add(val)
print (output)

chiqdi:

[['1', '2'], ['3', '4'], ['5', '6'], ['7', '8']]
1
qo'shib qo'ydi
O (n) ishlash vaqti.
qo'shib qo'ydi muallif Vikash Singh, manba
Xohlagan xarajatlarni ham eslatib o'ting. O'ylaymanki, u (n) bor. shundaymi?
qo'shib qo'ydi muallif Awais, manba
List length: n
Element length: m 
Complexity: 
    Iterate on n
    Format key by iterating on m
    Check key exists is set `uniques` in O(1)
    Total running time is is O(n * m)

Buning oddiy usuli:

uniques = set()
output = []
for x in A:
    val = '-'.join([str(key) for key in x])
    if val not in uniques:
        output.append(x)
        uniques.add(val)
print (output)

chiqdi:

[['1', '2'], ['3', '4'], ['5', '6'], ['7', '8']]
1
qo'shib qo'ydi
O (n) ishlash vaqti.
qo'shib qo'ydi muallif Vikash Singh, manba
Xohlagan xarajatlarni ham eslatib o'ting. O'ylaymanki, u (n) bor. shundaymi?
qo'shib qo'ydi muallif Awais, manba

Yana bir potentsial oddiy echim, ammo "xarajat" boshqa taklif qilingan echimlarga qanday qilib taqqoslash mumkinligiga ishonch emas:

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

res = []
for entry in A:
    if not entry in res:
        res.append(entry)
1
qo'shib qo'ydi
Taqdim etilgan ma'lumotlar uchun ushbu echim juda mos, tartib-saqlab turuvchi va qabul qilinganidek sodda. 10000 ta ro'yxatning 1000 ta raqami uchun qimmat bo'lishi mumkin.
qo'shib qo'ydi muallif 9000, manba

Bu oddiy qaror:

In [27]: A = [['1','2'],['3','4'],['5','6'],['1','2'],['3','4'], ['7','8']]

In [28]: new_list = []

In [29]: for i in A:
    ...:     if i not in new_list:
    ...:         new_list.append(i)
    ...:         

In [30]: new_list
Out[30]: [['1', '2'], ['3', '4'], ['5', '6'], ['7', '8']]
1
qo'shib qo'ydi
agar new_list ichida bo'lmasa: bu qimmatli qadammi va jarayonni n ^ 2 amalga oshiradimi?
qo'shib qo'ydi muallif Vikash Singh, manba
Xohlagan xarajatlarni ham eslatib o'ting. O'ylaymanki, u (n) bor. shundaymi?
qo'shib qo'ydi muallif Awais, 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