Portál AbcLinuxu, 18. říjen 2017 19:04

Dotaz: Specifický merge dvou polí

11.8.2016 09:22 RM
Specifický merge dvou polí
Přečteno: 1507×
Odpovědět | Admin
Mám jeden zajímavý úkol, dokáže někdo nabídnout řešení? Jsou dva seznamy (tedy pole) a já potřebuji z druhého seznamu vyházet prvky, které jsou v poli prvním, ale ne všechny -- jen takový počet, jaký je jich v tom prvním seznamu (pokud se tam vyskytuje prvek B dvakrát, pak budou odstraněny první dva prvky B z druhého seznamu, ale další zůstanou). Moc hezky se to dá udělat v Perlu. Co mě ale zajímá je, jestli se najde i nějaký jiný programovací jazyk, který by to dokázal provést jako one-liner či něco podobného velmi krátkého (pokud možno bez for/while cyklů).

Řešení dotazu:


Nástroje: Začni sledovat (1) ?Zašle upozornění na váš email při vložení nového komentáře.

Odpovědi

Řešení 1× (Vladimír Čunát)
11.8.2016 13:50 ttt
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Odpovědět | | Sbalit | Link | Blokovat | Admin
Haskell:
Prelude Data.List> [1,2,2,3,3,3,4,4,4,4] \\ [4,4,3,3,2,2,1,1]
[3,4,4]
/thread :)
11.8.2016 16:39 Andrej | skóre: 44 | blog: Republic of Mordor | Zürich
Rozbalit Rozbalit vše Re: Specifický merge dvou polí

Tady je Python, styl „prase psalo“. Bylo by to mnohem přehlednější i kratší, kdyby to nemusel být oneliner. :-)

listsub = lambda first, second: [i for d in ([(d, d.update(((k, 1 + d.get(k, 0)),))) for d in ({},) for k in first][0][0],) for i in second if (d.get(i, 0), d.update(((i, d.get(i, 0) - 1),)))[0] <= 0]

A takhle se to dá vyzkoušet:

listsub([1, 1, 1, 5, 5, 4, 3, 4, 3, 4, 3], [5, 4, 3, 2, 1] * 10)
listsub([4, 4, 3, 3, 2, 2, 1, 1], [1, 2, 2, 3, 3, 3, 4, 4, 4, 4])

Kdyby to nebyl oneliner:

def listsub_gen(first, second):
    counts = {}
    for i in first:
        counts.setdefault(i, 0)
        counts[i] += 1
    for i in second:
        if counts.get(i, 0):
            counts[i] -= 1
        else:
            yield i

def listsub(first, second):
    return [i for i in listsub_gen(first, second)]
ǑǦŹǓǕǙǞǺǨȞȬḔḦḰḾṊṎṸẄẌỖ
11.8.2016 19:04 RM
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Tohle není moc podle mého gusta, ale díky za ukázku.
23.8.2016 01:19 gl
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
V pythonu se dá použít kolekce Counter
>>> from collections import Counter
>>> list((Counter([1,1,3,2,2])-Counter([1,2,2,2])).elements())
[1, 3]
24.8.2016 17:14 Andrej | skóre: 44 | blog: Republic of Mordor | Zürich
Rozbalit Rozbalit vše Re: Specifický merge dvou polí

Ano, použít se dá, ale uvedené řešení nesplňuje zadání.

>>> listsub([2], [3, 2, 1])
[3, 1]

list((Counter([3, 2, 1]) - Counter([2])).elements())
[1, 3]

Bylo by potřeba procházet seznamem, postupně odebírat prvky z counteru a ty, kterých už je nula, dát do výsledného seznamu.

ǑǦŹǓǕǙǞǺǨȞȬḔḦḰḾṊṎṸẄẌỖ
24.8.2016 21:39 gl
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Můžu to seřadit podle indexů prvního listu.
list(sorted((Counter(a)-Counter(b)).elements(), key=a.index))
případně efektivněji
list(sorted((Counter(a)-Counter(b)).elements(), key=dict(zip(a,range(len(a)))).get))
pavlix avatar 24.8.2016 18:53 pavlix | skóre: 54 | blog: pavlix
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
return [i for i in listsub_gen(first, second)]
Ehm...
return list(listsub_gen(first, second))
24.8.2016 20:22 Andrej | skóre: 44 | blog: Republic of Mordor | Zürich
Rozbalit Rozbalit vše Re: Specifický merge dvou polí

Tak to je zásadní, převratné a dech beroucí zlepšení, opravdu.

ǑǦŹǓǕǙǞǺǨȞȬḔḦḰḾṊṎṸẄẌỖ
24.8.2016 23:56 gl
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Zásadní to není, ale ten kód je zbytečně delší.
11.8.2016 19:01 RM
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
To vypadá dobře. A co kdybych chtěl vyházet prvky prvního seznamu bez ohledu na počet stejných prvků v druhém seznamu. Například: jedna položka 4 odstraní všechny položky 4 v prvním seznamu. To se zdá být jednodušší, tudíž jsem to do dotazu nepsal, ale i tohle by mě zajímalo.
12.8.2016 13:06 ttt
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Prelude Data.List> filter (`notElem` [1,2,3]) [1,1,2,2,3,3,3,4,4,4,4]
[4,4,4,4]
13.8.2016 16:55 RM
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Díky! Zeptal jsem se na něco jiného, jak je asi jasné z mé odpovědi s ukázkou v perlu. To co jsem před časem řešil bylo odstranění jen prvního prvku z pole A bez ohledu, kolikrát se tento prvek vyskytuje v B. Tedy to, pro co používám substituci s g. To, na co jsem se dodatečně zeptal, se v perlu udělá jen pomocí grepu a regulárního výrazu s negací, nic až tak zajímavého.
11.8.2016 19:07 RM
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Odpovědět | | Sbalit | Link | Blokovat | Admin
Jinak se omlouvám, mělo to asi patřit do Programovací poradny. Klidně to tam může někdo přesunout, pokud to jde.
wamba avatar 11.8.2016 19:53 wamba | skóre: 37 | blog: wamba
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Odpovědět | | Sbalit | Link | Blokovat | Admin
A to hezké řešení v Perlu nám ukážeš? Pokud netrváš na zachování pořadí prvků v poli, tak v Perlu 6:
perl6 -e 'my $a=(2,2,1,1,1,7).Bag;my $b=(1,2,1,3,1,2,2,1,2,3,1,4).Bag; say  ($b (-) $a).kxxv'
pokud by si trval, tak třeba:
perl6 -e 'my $a=(2,2,1,1,1,7).BagHash; my @b=(1,2,1,3,1,2,2,1,2,3,1,4);  say @b.grep: { !$a{$_}-- }'
This would have been so hard to fix when you don't know that there is in fact an easy fix.
11.8.2016 20:53 RM
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Pěkné pěkné! Ve starém perlu stačilo použít trik s regulárním výrazem. Plus bylo třeba znát prioritu operátorů (stačí že not má tu nejnižší, && funguje stejně jako v shellu, {pro nezasvěcené}):
perl -le '@pole1=(4,4,3,3,2,2,1);@pole2=(1,2,2,3,3,3,4,4,4,4);  $regx=join "\|", @pole1; print grep { not /^$regx$/ && $regx =~ s/\|?$_\|?/|/ } @pole2'
Pro druhý případ stačí provést substituci globálně (g). Nevypadá to asi nic extra, ale lepší než šolichání v cyklech, které mne vedle toho napadlo.
13.8.2016 16:59 RM
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Ta substituce je samozřejmě zbytečně složitá: pro seznam bez prázdných prvků stačí jen s/$_//. Pro prázdné prvky by musel být výraz ještě trochu vylazen.
23.8.2016 01:26 gl
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
tohle mi vyhodí hlášku:
No such method 'kxxv' for invocant of type 'Bag'
co má dělat kxxv?
wamba avatar 23.8.2016 05:45 wamba | skóre: 37 | blog: wamba
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Přemění to Bag, což je specifický Hash, na pole.
perl6 -e 'my $a=(2,2,1,1,1,7).Bag;my $b=(1,2,1,3,1,2,2,1,2,3,1,4).Bag; 
say ($b (-) $a);         #bag(4, 3(2), 1(2), 2(2))
say ($b (-) $a).Hash;    #{1 => 2, 2 => 2, 3 => 2, 4 => 1}
say ($b (-) $a).kxxv;    #(4 3 3 1 1 2 2)
my &my-kxxv =  {flat .keys Zxx .values}; 
say my-kxxv $b (-) $a;   #(4 3 3 1 1 2 2)
'
This would have been so hard to fix when you don't know that there is in fact an easy fix.
24.8.2016 16:08 gl
Rozbalit Rozbalit vše Re: Specifický merge dvou polí
Dík za odpověď. Na novější verzi Perlu6 to funguje. Koukám, že Perl6 toho umí out of box opravdu hodně.

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267, (c) 1999-2007 Stickfish s.r.o.