-
X-Received: by 10.31.147.5 with SMTP id v5mr5020294vkd.5.1517850822034; Mon, 05 Feb
2018 09:13:42 -0800 (PST)
X-Received: by 10.31.147.5 with SMTP id v5mr5020294vkd.5.1517850822034; Mon, 05 Feb
2018 09:13:42 -0800 (PST)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!news.unit
0.net!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.
iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!q21no80
7459qtn.1!news-out.google.com!u51ni301qtk.1!nntp.google.com!t22no396843qtb.0!po
stnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Mon, 5 Feb 2018 09:13:41 -0800 (PST)
In-Reply-To: <p59k3h$ofh$1@node1.news.atman.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.39.182;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 159.205.39.182
References: <p587gc$652$1@node2.news.atman.pl> <p588eh$71r$1@node2.news.atman.pl>
<e...@g...com>
<p59k3h$ofh$1@node1.news.atman.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c...@g...com>
Subject: Re: Ktoś używał 1000genomes? Diff
From: "M.M." <m...@g...com>
Injection-Date: Mon, 05 Feb 2018 17:13:42 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 45
Xref: news-archive.icm.edu.pl pl.comp.programming:212268
[ ukryj nagłówki ]On Monday, February 5, 2018 at 1:53:06 PM UTC+1, Borneq wrote:
> W dniu 05.02.2018 o 10:31, M.M. pisze:
> > Dziedzina wiedzy dziedziną wiedzy, ale porównania się robi i używa się
> > do tego analogicznych algorytmów jak do porównywania ciągów znaków.
>
> Czytałem o algorytmie Myersa wspaniale wytłumaczonym na blogu jcoglan.
> Znajduje maksymalny wspólny podciąg, ale rozwiązań może być wiele. W
> podstawowej wersji ma tę miłą właściwość że gromadzi inserty i delety
> razem. Jednak wersja profesjonalna, używająca liniowego a nie
> kwadratowego miejsca pamięci, nie ma tej właściwości.
> Przykład:
> https://blog.jcoglan.com/2017/03/22/myers-diff-in-li
near-space-theory/
>
> Jak można by to poprawić? Może najpierw rekurencyjnie dzielić na bloki,
> ale gdy blok nie przekracza 50 wierszy, robić wersję standardową?
> Poza tym, implementacja Butlera z CodeProject dla liniowego:
> 782104906830590
> 683059078210490
> daje lepsze rezultaty niż można by się spodziewać.
>
> Git ma jeszcze możliwość opcji --patience, która poprawia, jednak
> wyszukując unikalne wiersze - nie nadaje się np. do genomu.
Z tego co pobieżnie kiedyś dawno temu przeglądałem, to temat jest
niebagatelny, ponieważ istnieje wiele heurystyk. Poszczególne
heurystyki różnie podnoszą skuteczność pamięciową i/albo obliczeniową
w zależności od danych; głównie chodzi o to, na ile porównywane
podciągi są podobne. Przy złożoności obliczeniowej M*N
ciężko policzyć dla choćby miliona genów, nie wspominając o
pamięciowej.
Pozdrawiam
Następne wpisy z tego wątku
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-12 Afera II LO w Nowym Sączu wypracowanie
- 2024-05-12 rezystor 3 omy 400W
- 2024-05-12 Dwukabinowy Citroen - dziwadło pod zabudowę spec
- 2024-05-12 Co oznacza Wi-Fi? - po prostu nic!
- 2024-05-11 Chess
- 2024-05-11 Chess
- 2024-05-11 Vitruvian Man - parts 7-11a
- 2024-05-11 Vitruvian Man - parts 7-11a
- 2024-05-11 Katowice => Administrator IT - Wirtualizacja i Konteneryzacja <=
- 2024-05-11 Poznań => Business Development Manager - obszar bezpieczeństwa IT <=
- 2024-05-11 Vitruvian Man - parts 1-6
- 2024-05-11 Vitruvian Man - parts 1-6
- 2024-05-11 Wrocław => Lider Serwisu/Programista PLC z językiem niemieckim <=
- 2024-05-11 Czy dopłaty do używanych elektryków z Niemiec będą również do czterokołowców lekkich?
- 2024-05-11 Warszawa => Interactive/Experience Designer <=