Article View: pl.comp.programming
Article #215806Re: "Najbardziej imponujący kod, jaki widziałem"
From: Maciej Sobczak
Date: Tue, 06 Aug 2019 08:55
Date: Tue, 06 Aug 2019 08:55
35 lines
3958 bytes
3958 bytes
> > Prosta sprawa - zmodyfikuj rozwiązanie w Mathematice tak, żeby koszt zamiany elementu wynosił 2 a nie 1.
>
> Pytanie jest fair i odpowiedź (również fair) jest taka: sam sobie policz.
OK, żeby nie było, że jestem nieuprzejmy, i dla własnej zabawy, zrobiłem mały research w tej sprawie.
Jest taka fajna funkcja:
https://reference.wolfram.com/language/ref/SequenceAlignment.html
Ta funkcja rozpisuje różnice między sekwencjami, z czego można wyciągnąć poszczególne operacje (usunięcie, wstawienie, zamiana). Jeżeli dobrze zrozumiałem ćwiczenie, to rozwiązeniem może być takie coś:
myDistance[s1_, s2_] := Total[
Min[#] + Max[#] & /@
Cases[SequenceAlignment[s1, s2], a_List :> StringLength /@ a]
]
Pozwoliłem sobie użyć skróconych (idiomatycznych) zapisów na podstawowe operacje mapowania i lambdy - skoro w innych językach są śmieszne znaczki, to ja też skorzystam.
Wyrażenie Min+Max załatwia podwójne zliczenie zamian w porównaniu do wstawień/usunięć. Pełne wyrażenie dla dowolnych wag to:
replacementCost*Min[#] + deletionCost*(Max[#] - Min[#])
gdzie # to anonimowa para {del, ins}, gdzie del to ilość znaków do usunięcia a ins to ilość znaków do wstawienia; jeśli obie są niezerowe, to znaczy, że jest zastąpienie, więc np. para {3,5} oznacza, że są 3 znaki do zastąpienia i 2 do usunięcia/wstawienia. Wszystkie takie wartości są sumowane.
Czy to jest prawidłowy sposób liczenia - nie wiem, ale tak to zrozumiałem.
Czyli nadal nie wyszło jakoś dramatycznie dużo tego kodu, prawda?
Nadal jednak szukałbym gotowych implementacji tutaj (choćby po to, żeby skorzystać z optymalizacji, które ktoś zrobił za mnie):
https://reference.wolfram.com/language/guide/DistanceAndSimilarityMeasures.html
I właśnie na tym polega użyteczność tego produktu.
--
Maciej Sobczak * http://www.inspirel.com
Technical Details
Message-ID:
<c4e3147c-61af-4b8b-86f2-9e367e44b228@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!takemy.news.telefonica.de!telefonica.de!weretis.net!feeder7.news.weretis.net!news.mixmin.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!b26no5870406qtq.0!news-out.google.com!a5ni1344qtd.0!nntp.google.com!b26no5870398qtq.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailReferences:
<edc55064-0038-4844-a994-4cddd7d77d76@googlegroups.com> <11e4b1d7-2d97-48ac-8a3d-9172df46bf0b@googlegroups.com> <c10e995b-108e-4770-840c-f27c95c0d36c@googlegroups.com> <004de5cc-bf54-4740-92d9-d7f5892c68f1@googlegroups.com> <ba268c8f-c446-4d4c-93e9-b640ebd0f75e@googlegroups.com> <d570836b-f9da-4359-b307-981afc6d4b40@googlegroups.com> <2f6d1e89-c868-49ad-bf88-81e0560f48c9@googlegroups.com> <cff169cc-d481-4ded-ba90-43d0f5ecc05e@googlegroups.com> <b9c338d3-c80c-4b42-99ff-da12417126b7@googlegroups.com> <10218256-a88b-4be5-9815-723d2b757225@googlegroups.com> <ae20996a-1fd5-44dc-a39e-e627c633cc06@googlegroups.com> <e8792740-b3b1-48c6-917f-1dfb1fe8bab1@googlegroups.com>Show Full Headers
Complete Article Headers
X-Received: by 2002:a05:620a:16a6:: with SMTP id s6mr2139450qkj.39.1565081704289; Tue, 06 Aug 2019 01:55:04 -0700 (PDT) X-Received: by 2002:ac8:25b1:: with SMTP id e46mr2069724qte.36.1565081704145; Tue, 06 Aug 2019 01:55:04 -0700 (PDT) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!takemy.news.telefonica.de!telefonica.de!weretis.net!feeder7.news.weretis.net!news.mixmin.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!b26no5870406qtq.0!news-out.google.com!a5ni1344qtd.0!nntp.google.com!b26no5870398qtq.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.programming Date: Tue, 6 Aug 2019 01:55:03 -0700 (PDT) In-Reply-To: <e8792740-b3b1-48c6-917f-1dfb1fe8bab1@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=194.9.245.29; posting-account=bMuEOQoAAACUUr_ghL3RBIi5neBZ5w_S NNTP-Posting-Host: 194.9.245.29 References: <edc55064-0038-4844-a994-4cddd7d77d76@googlegroups.com> <11e4b1d7-2d97-48ac-8a3d-9172df46bf0b@googlegroups.com> <c10e995b-108e-4770-840c-f27c95c0d36c@googlegroups.com> <004de5cc-bf54-4740-92d9-d7f5892c68f1@googlegroups.com> <ba268c8f-c446-4d4c-93e9-b640ebd0f75e@googlegroups.com> <d570836b-f9da-4359-b307-981afc6d4b40@googlegroups.com> <2f6d1e89-c868-49ad-bf88-81e0560f48c9@googlegroups.com> <cff169cc-d481-4ded-ba90-43d0f5ecc05e@googlegroups.com> <b9c338d3-c80c-4b42-99ff-da12417126b7@googlegroups.com> <10218256-a88b-4be5-9815-723d2b757225@googlegroups.com> <ae20996a-1fd5-44dc-a39e-e627c633cc06@googlegroups.com> <e8792740-b3b1-48c6-917f-1dfb1fe8bab1@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <c4e3147c-61af-4b8b-86f2-9e367e44b228@googlegroups.com> Subject: Re: "Najbardziej imponujący kod, jaki widziałem" From: Maciej Sobczak <see.my.homepage@gmail.com> Injection-Date: Tue, 06 Aug 2019 08:55:04 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit