-
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
- 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?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-04-24 Warszawa => Software Engineer .Net <=
- 2024-04-24 Gdańsk => Mid PHP Developer (Laravel) <=
- 2024-04-24 Wrocław => Head of Sales (IT services/products field) <=
- 2024-04-24 Warszawa => Spedytor międzynarodowy <=
- 2024-04-23 Dostałem nową kartę
- 2024-04-23 Re: Głośniki
- 2024-04-23 Re: Głośniki
- 2024-04-23 Fwd: Re: Głośniki
- 2024-04-23 Re: Głośniki
- 2024-04-23 Białystok => Senior Rust Software Engineer <=
- 2024-04-23 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-04-23 Czy prawo okresli granice chamstwa Jońskiego?
- 2024-04-23 Warszawa => Manager Sprzedaży <=
- 2024-04-23 Kraków => Service Leader/PLC Programmer with German <=
- 2024-04-23 Białystok => Senior Software Engineer PHP (BillPro) Kontraktor <=