ELSCR elegantně
Školení, která pořádám 
Jirka Knesl představil JavaScriptovou funkci, která převádí znaky „ěľščř“ a další na jejich číselné varianty podle umístění na české a slovenské klávesnici. Myšlenka to není originální, tak jsem se alespoň podíval na implementaci a dost jsem se zhrozil:
- Rekurze hluboká 15 pater pro jednoduchý vstup „+ééé“.
- Časová složitost O(N²).
- Pět metod.
- Nepodporuje moje rozložení klávesnice.
Vždyť je to úplně jednoduchá věc:
/** Převod českých a slovenských znaků na čísla podle jejich místa na klávesnici
* @param string
* @returns string
* @author Jakub Vrána, https://php.vrana.cz/
*/
function elscr(value) {
var map = { '+': 1, 'ů': 1, 'ě': 2, 'ľ': 2, 'š': 3, 'č': 4, 'ř': 5, 'ť': 5, 'ž': 6, 'ý': 7, 'á': 8, 'í': 9, 'é': 0 };
return value.replace(/[+ůěľščřťžýáíé]/g, function (match) {
return map[match];
});
}
Na této triviální implementaci zapáchá jedna věc: Seznam znaků je na dvou místech, takže když bychom v budoucnu chtěli přidat další převod, museli bychom to udělat dvakrát. V moderním JavaScriptu bychom na získání klíčů objektu mohli použít funkci Object.keys, ve starších verzích to musíme udělat trochu jinak:
function elscr(value) {
var source = '+ůěľščřťžýáíé';
var target = '1122345567890';
var map = { };
for (var i = 0; i < source.length; i++) {
map[source[i]] = target[i];
}
var pattern = new RegExp('[' + source.replace(/[-\]^\\]/g, '\\$&') + ']', 'g');
return value.replace(pattern, function (match) {
return map[match];
});
}
Dalo by se to dále zrychlit vybudováním regulárního výrazu mimo hlavní funkci, ale vzhledem k primárnímu využití to nepovažuji za nutné. Vypadalo by to takhle:
var elscr = (function () {
var source = '+ůěľščřťžýáíé';
var target = '1122345567890';
var map = { };
for (var i = 0; i < source.length; i++) {
map[source[i]] = target[i];
}
var pattern = new RegExp('[' + source.replace(/[-\]^\\]/g, '\\$&') + ']', 'g');
return function elscr(value) {
return value.replace(pattern, function (match) {
return map[match];
});
}
})();
Diskuse
KindleMan:
Ahoj Jakube,
nebylo by vhodné do této metody rovnou implementovat ochranu vstupu jen na čísla. Takže by při psaní povolila jen čísla a přepisovala source znaky.
Díky
Bronzi:
A co třeba dle mého ještě krásnější:
<?php
function elscr(value) {
var map = { '+': 1, 'ů': 1, 'ě': 2, 'ľ': 2, 'š': 3, 'č': 4, 'ř': 5, 'ť': 5, 'ž': 6, 'ý': 7, 'á': 8, 'í': 9, 'é': 0 };
var ret = '';
for (var i = 0; i < value.length; i++){
if(map[value[i]] !== undefined) ret += map[value[i]];
else ret += value[i];
}
return ret;
}
?>
Bronzi:
PS. Samozřejmě že to není PHP kód jen jsem chtěl aby se zvýraznil :-)
Martin Hořínek:
Není to krásnější.Btw. celkově pod článkem krásná diskuze :)
Martin Soušek:
No jo, jenže tvé řešení má také řadu fatálních nevýhod:- není agilní
- není napsané čistě funkcionálně
- chybí testy
- není ve veřejném git úložišti
- je v obyčejném javascriptu nikoliv ve skvělém livescriptu
- nepoužívá samodokumentující se názvy proměnných (například nicneříkající "i" v cyklu místo správného "this-is-our-cool-loop-index-variable")
Uvědom si, že dnešní programátorské hodnoty jsou úplně jinde. Hloubka rekurze? Časová složitost? Zastaralá sprostá slova!
Martin Štekl:
Dovoluji si nesouhlasit s poslední větou. Neříkám, že hloubku rekurze a časovou složitost řeším na denní bázi, ale rozhodně jsem to už několikrát musel řešit (asi 10x za posledních cca 4,5 roku). Nebýt toho, že něco takového člověk zná a vyzná se v tom, nebyl bych schopen chybný kód opravit. A předem říkám, že se nejednalo o žádnou školní úlohu, ale že jsem na to narazil v praxi. Stejně jako tohle člověk musí znát, co se vejde do Integer hodnoty v tom kterém programovacím jazyce na které architektuře.
Na druhou stranu je pravda, že u takto jednoduchého skriptu nemá moc smysl něco podobného řešit. Samozřejmě dokud nebudeme chtít nahrazovat všechny znaky UTF-8 ;-)
Souhlasím naopak se všemi napsanými (chybovými) body. Beru však tento článek jen jako ukázku toho, jak by k tomu přistupoval Jakub. Stejně tak jsem rád, že stále mluví o hloubce rekurze a časové složitosti. Tyhle znalosti osobně beru jako zásadní rozdíl mezi „programátorem“ a „programátorskou opicí“.
Martin Štekl: 
Jakub Vrána 
:
Já se snažím psát algoritmy tak, aby nebyly zbytečně pomalé a přitom je to moc nezkomplikovalo. Např. jsem alergický na takovýto kód s časovou složitostí O(N²):
<?php
// Pole $a a $b jsou podobně veliká.
foreach ($b as $val) {
if (in_array($val, $a)) {
echo array_search($val, $a);
}
}
?>
Přitom se dá napsat skoro stejně jednoduše, ale s časovou složitostí O(N):
<?php
// Za předpokladu, že hodnoty $a jsou skalární.
$a_flipped = array_flip($a);
foreach ($b as $val) {
if (isset($a_flipped[$val])) {
echo $a_flipped[$val];
}
}
?>
Někdo by to možná označil za předčasnou optimalizaci, ale ona to je desetinka k desetince, čtvrt sekundy tuhle a rázem se stránka nahrává pět sekund, aniž by měla zjevné úzké hrdlo.
Totéž platí pro dotazy do tabulek s více než pár desítkami záznamů bez indexu, kladení dotazů v cyklu a podobně.
Jakub Vrána : v6ak:
Není to spíš O(n*log(n))?
Ale jinak souhlas.
Jakub Vrána :
Ne. $a_flipped[$val] je amortizovaně O(1), takže celkem to je skutečně O(N).
Jakub Vrána : v6ak:
Pokud $a_flipped bude odpovídat typu Map[String, _], pak přístup v O(1) se dá udělat snad jen s bezkolizní hashovací funkcí pro String nebo podobnou specialitou. Což moc dobře nejde (v obecném případě), nemá-li to pole v paměti zabírat množství paměti exponenciálně rostoucí s délkou nejdelšího řetězce.
Pro relativně hustá čísla by to šlo konstantně snadno (typ analogický k Vector[_]).
Přemýšlím, jestli je možné nějak dokázat, že to nejde v O(1) v obecném případě (tj. mám tak nanejvýš operace _>_, _<_, _==_ a _.hashCode). Je to snadné dokázat u řešení, ze kterých lze v O(n) vyčíst seřazenou posloupnost klíčů (např. binární vyhledávací strom) - pak bych uměl i řadit v O(n). Nevím ale, jak to dokázat pro ostatní.
Jakub Vrána :
Hashovací funkce nemusí být bezkolizní. Stačí, aby kolizí nebylo víc než konstanta. A to v PHP platí, tedy až na zákeřnosti jako http://php.vrana.cz/zakerne-pole.php, ale i pro ty je už to myslím vyřešené (funkce je randomizovaná).
O(N) je to samozřejmě při omezené délce klíče (která je obvykle zanedbatelná). Pokud bychom ji chtěli zohlednit, tak to bude O(M*N), kde M je průměrná délka klíče. Lépe to nejde, protože musíme všechny klíče aspoň přečíst.
Jakub Vrána : v6ak:
Jasný, délka klíče se nám nejspíš projeví v operacích _<_, _>_, _==_ a _.hashCode (i když u _.hashCode ne nutně; to mi ale stejně asi nepomůže). Já ji zanedbal jakožto konstantní, což je chyba.
Hashovací tabulka má dva extrémy - O(1*m) a O(n*m) (popř. O(1) a O(n), zanedbáme-li m). Většinou je blíž O(1), ale je otázka, kde je průměr.
rus:
On spíše Jirka Knesl vůbec JavaScript nezná a neví o tom, že existuje metoda replace() a něco jako regulární výrazy, proto je to napsáno tak složitě. Je hezká ukázka toho, že se lze prosadit, i když člověk nic neumí.Karel:
Jakube, kdy očekáváte, že na české klávesnici přibudou další znaky pro převod? Já doufám, že brzy, například pod anglickou klávesou pro číslo 10 by mohlo být ô, abych mohl snadněji oslovovat své slovenské kolegy. Jakub Vrána :
Za poslední týden do mapy přibyly tři znaky ve dvou vlnách. Tímhle tempem máme do roka 100 změn a 150 nových znaků :-).
Jakub Vrána : Marian Hello:
Pripravil som porovnanie výkonu jednotlivých implementácií.http://jsperf.com/elscr-perf
Implementácie p. Knesla je o 84% pomalšia ako Jakubova implementácia.
Rozdiel medzi closure (vybudováním regulárního výrazu mimo hlavní funkci) a non-closure je zanedbateľný.
Milsa:
Aké to má využitie?
Lolobrigida:
Stojí ti potom 2x déle.Milsa (msx):
Veď práve. Aká je tu okolo toho divoká diskusia a zatiaľ ma nenapadol jediný dôvod na čo to vôbec programovať.
v6ak:
Tak jsem se to pokusil implementovat jednoduše v čistém JS. funkci replace jsem zneužil jako funkci map:
<?php // jinak si nejsem jist s formátováním
function elscr(value){
var map = { '+': 1, 'ů': 1, 'ě': 2, 'ľ': 2, 'š': 3, 'č': 4, 'ř': 5, 'ť': 5, 'ž': 6, 'ý': 7, 'á': 8, 'í': 9, 'é': 0 };
return value.replace(/./g, function(c){
return map[c] || c;
});
}
?>
Dá někdo jednodušší?
Filip Procházka:
Moc pěkné, ale nebude to pomalejší, když se teď volá callback pro každý znak?
Petr Sýkora:
Při přidání normálních čísel do testovacího vzorku ješte pomalejší. Což mi přijde zajímavé, vzhledem k tomu, že lze předpokládat, že část uživatelů nejspíč napíše čísla správně. Viz http://jsperf.com/elscr-perf/3Filip Procházka:
Ještě bych upravil bych regulár na
<?php return value.replace(/[^d]/g, function(c){..} ?>
Anyway, tyhle měření jsou stejně fuk. Jak dlouhá čísla běžně píšete? Dokud bude mít řetězec pár znaků, maximálně desítky, tak to můžete nahrazovat klidně i bagrem :) Tím samozřejmě nechci omlouvat Jirkovo přehnaně složité řešení.
Filip Procházka:
Samozřejmě jsem myslel:
return value.replace(/[^\\d]/g, function(c){..}
Jakube, zlobí ti zvýrazňovátko.
Jakub Vrána :
Zvýrázňovátko funguje, ale zvýrazňuje PHP kód… Navíc tohle je taky blbě, správně má být /[^\d]/g nebo rovnou /\D/g.
Jakub Vrána : v6ak:
Jasný. Hlavně když je to lineární :)
Jakub Vrána :
To je pěkné řešení. Je fakt, že u mého druhého a třetího řešení už to začíná být dost krkolomné taky.
Jakub Vrána : Stefan Fiedler:
Mozna proto, ze jsem lama, me hned po precteni poloviny clanku napadlo toto. Nevim jestli to bude rychle nebo pomale, ale prijde mi to jednoduche :-)function elscr(vstup){
var map = {'+':'1','ů':'1','ě':'2','ľ':'2','š':'3','č':'4','ř':'5','ť':'5','ž':'6','ý':'7','á':'8','í':'9','é':'0'};
var vystup = '';
var i = vstup.length;
while(i--) {
vystup = (map[vstup[i]] || vstup[i]) + vystup;
}
return vystup;
}
Jakub Vrána :
Postupné skládání řetězce může v obecných případech trochu zdržovat (každé zvětšení řetězce znamená uvolnit ho z paměti, alokovat trochu víc místa a zase ho do ní šoupnout), to ale platí pokud vím jen pro IE, možná navíc jen starší verze (ostatní prohlížeče si nechávají rezervu, takže k realokaci tak často nedochází). Z tohoto důvodu se často kousky řetězce dávají do pole, které se na konci jen spojí.
Ale tady to není potřeba řešit, protože řetězec nebude moc dlouhý. Je to dobré řešení.
Jakub Vrána : Stefan Fiedler:
Diky moc za tip s tim polem Jakube, to budu urcite pouzivat. Navic to presypavani do pole ma i prehlednejsi kod pri prochazeni stringu pozpatku.bene:
<?php // zvyrazneni syntaxefunction Elscr() {
var map = {'+': 1, 'ů': 1, 'ě': 2, 'ľ': 2, 'š': 3, 'č': 4, 'ř': 5, 'ť': 5, 'ž': 6, 'ý': 7, 'á': 8, 'í': 9, 'é': 0};
var regExpChars = '';
for (var key in map) {
regExpChars += key;
}
var regExp = new RegExp('[' + regExpChars + ']', 'g');
this.replace = function(value) {
return value.replace(regExp, function(match){
return map[match];
});
};
}
var elscr = new Elscr();
elscr.replace('+ěš');
?>
Vytvoření regulárního výrazu se provede jednou. Možnost rozšíření.
Jakub Vrána :
To je jen krkolomnější verze poslední varianty z článku.
Jakub Vrána : bene:
To je věc názoru. Troufám si tvrdit že pro spoustu programátorů, kteří nemají s JavaScriptem velké zkušenosti, bude kostrukce<?php
var elscr = (function () {
// ...
return function elscr(value) {
return value.replace(pattern, function (match) {
return map[match];
});
}
})();
?>
mnohem hůře čitelná/pochopitelná.
Chtěl jsem pouze ukázat jinou formu, která mi navíc umožní do budoucna rozšiřitelnost (je otázka jestli je to v tomto případě výhoda, ale více kódu a složitějšího kódu to není, tak proč to tak neudělat).
Franta:
1) Hloubka rekurze nemusí být problém, pokud jde o tzv. koncovou rekurzi: https://duckduckgo.com/?q=tail+recursion (nevím, jestli je to ten případ a jestli je to podporované danou implementací JS, ale obecně bych hlubokou rekurzi takto šmahem nezavrhoval)
2) Detaily jsem nezkoumal, ale řešit prostou substituci znaků na sedmdesáti řádcích kódu mi přijde trochu zbytečné.
3) Přepisovat celý obsah pole (včetně obsahu, který třeba ani teď uživatel nenapsal), když chceme přepsat jen aktuálně stisknutou klávesu, mi přijde hloupé. Ale nevím, jestli to v tomhle jazyce jde udělat líp.
4) Počítal jsi předem, kolik výkonu to sežere? Přijde mi, že vzhledem k tomu, kde to běží (počítač klienta, se kterým pracuje jeden uživatel) a jak to běží (odezva na stisky kláves, jednotky znaků) nemá smysl nějaké optimalizace řešit – nějaké zrychlení/zpomalení bude zřejmě hluboko pod rozlišovací schopností uživatele. A větrák CPU se asi rychleji neroztočí a baterku v mobilu to taky nesežere. (něco jiného by bylo např. vykreslování stromu nebo tabulky o tisících položek, tam už by zpomalení způsobené neefektivním algoritmem mohlo být znatelné) V zásadě by člověk měl vědět, v jakých řádech se pohybuje a řešit to, co má smysl a co má vliv na výsledek – nehrát si s blbostmi, které se neprojeví. (přehlednost a udržovatelnost kódu naopak smysl řešit má)
5) Nejsem si úplně jistý, jestli je dobré takové funkce do aplikací dávat… Na jednu stranu je to fajn a pohodlné, na druhou to ale vede k takovému mlhavému (místo exaktnímu) pojetí počítačů – v krajním případě to vede k tomu, že se ti po klávesnici projde kočka nebo na ni položíš hlavu, a ono nějakým záhadným způsobem uhodne, co jsi „chtěl“ (i když ve skutečnosti nechtěl) udělat, místo aby to ohlásilo chybu a odmítlo neplatný vstup.
v6ak:
K tail recursion doplním jednu zajímavost, kterou bych odhadoval, že budeš vědět: JVM to neumí. Z návrhů řešení jsem dokonce vyčetl, že by podpora vypadala tak, že by na to byla speciální složená instrukce (tedy před instrukce invoke{interface,virtual,static,dynamic} by se musela přidat instrukce vyzývající k TCO) a tedy zřejmě ta změna (asi kvůli stacktrace) není považována za zpětně kompatibilní. Dnes vím o jediném TCO nad JVM, ale to je omezené (jen pro rekurzi a jen při brzké vazbě) a implementované v kompilátoru Scaly.
U JS jsem také nenašel, že by to někdo implementoval, našel jsem ale http://wiki.ecmascript.org/doku.php?id=harm…_tail_calls , ale nestudoval jsem to podrobněji.
Jakub Vrána :
4. Nerad píšu bezdůvodně pomalé algoritmy. Časem se můžeme rozhodnout funkci použít třeba pro něco jiného. Pokud optimalizace funkce podstatně zvýší její složitost, tak se tomu vyhýbám (předčasná optimalizace), ale pokud je efektivní a neefektivní implementace zhruba stejně složitá, tak bez přemýšlení použiji tu efektivní. Viz příklad v http://php.vrana.cz/elscr-elegantne.php#d-13809.
Jakub Vrána : Diskobolos:
Chápu proč tento článek. Nicméně nasadit toto v praxi je pro návštěvníka stránek WTF. Už vidím svoji mámu, jak se diví, proč tam jo a tam ne, že má CZ klávesnici a co má dělat. No banalita, nicméně v praxi vidím využití pouze u čteček čarových kódů via "keyboard".L:
Tohle všechno je pro ty, co to omylem napíšou a pak se diví že to napsali špatně a musí to přepisovat. Tvoje máma asi schválně nebude psát "ě" místo dvojky.Franta:
Ale pak se budou divit jinde, že to nefunguje. Asi jako splachovadlo na záchodě, které se normálně zmáčkne, ale někdo by vymyslel, že bude splachovat, když se s ním zakroutí - a pak by se někteří lidé divili, že jiná splachovadla nesplachují, když s nimi kroutí.vbl:
No, sice to není splachovadlo, ale v Kanadě jsem byl v několika hotelích, v každém bylo ovládání kohoutku u umyvadla a vany jinak. Někde klasické dva kohourky, někde jedna páka, někde dvě. Někde se ty dvě páky nebo kohoutky otáčely stejným směrem, někdy proti sobě. Na jedné vaně byla dokonce cedulka s návodem, jak se to přepne na sprchu (protože vytáhnutí kroužku, ze kterého teče voda, nebylo vůbec intuitivní).Takže kraviny si lidi už vymýšlejí i u takovýchhle věcí :). Oproti tomu je replace paznehtů na čísla super věc.
Franta:
Pokud by se to ujalo, tak narazíš třeba u hesel – někdo bude zvyklý, že klávesa „č“ píše „4“ a bude se divit, že mu heslo nefunguje – jiný zase bude mít v hesle diakritiku a taky mu to nebude fungovat, když se náhodou bude přihlašovat do systému, který navrhoval nějaký „UI/UX ergonom“ a dal tam tuhle funkci.
Milsa (msx):
To je nezmysel. Pretože, keď používam slovenskú klávesnicu a budem tam mať v hesle slovenské znaky, tak ich aj budem chcieť zadať. Prečo by mi nejaká akože utilita mala vnucovať, že v hesle nebudem mať ť, ale 5? Nezmysel na n-tú. Keď niekde zadávam heslo, kde je Z alebo Y, tak si pozriem akú mám klávesnicu a podľa toho zadávam. Keby mám slovenskú klávesnicu a neberie mi správne napísané heslo, tak by mi to bolo divné. Keby zistím, že nejaká vymoženosť stránky si upravuje môj vstup, tak píšem email adminovi, že mi stránka neberie, čo zadávam alebo na stránku prestanem chodiť. A keď je niekto zvyknutý, že č píše 4, tak si tam dole pri hodinách zmení klávesnicu. V živote som tento nezmysel nepotreboval a zrazu sa tu nájde kopec ľudí čo to obhajuje, ale dôležité je uvedomiť si jedno. Používateľ si určil akú použije klávesnicu a tú chce aj použiť a nie šaškovať.
bene:
Očividně nechápete smysl této funkcionality.Vemte si HTML5 imput typu number. Na chytrém telefonu se Vám zobrazí klavesnice pouze s číslama. Dle Vaší logiky: "Proč mi vnucuje něco jiného, přece si čísla na klávesnici přepnu".
Nikdo Vám do hesla nevnucuje čísla místo znaků. Jedná se pouze o utilitu pro input typu number.
Takhle jsem to teda pochopil já.
Milsa (msx.):
Ja mám na to numerickú klávesnicu. Ale dobre, začínam tomu chápať. Problémom je, že to bude podporovať len určité klávesnice, takže toto riešenie nikdy univerzálne nebude.
Jiří Knesl:
Tady jsem vysvětlil, proč je kód implementovaný tímto způsobem:
http://knesl.com/articles/view/okomentovany-elscr-plugin
Franta:
Vrána je sice bastlíř, ale tady bych si vybral spíš jeho řešení – ovšem ne kvůli rychlosti, ale protože je přehlednější a lépe se čte i udržuje.Tvůj přístup je něco jako overengineering, ale skutečný overengineering má alespoň teoretický předpoklad, že v budoucnu ušetří práci a je připraven pružně reagovat na změny (na rozdíl od bastlu, kde je vše zadrátované).
Tenhle předpoklad tu ale bohužel nevidím. Je to pouze mentální cvičení (někdo by řekl onanie), které je sice smysl má, ale je potřeba to tak i otevřeně (a na začátku) přiznat (ne to prezentovat jako normální knihovnu, kterou by nedejbože někdo měl používat).
v6ak:
"ale je potřeba to tak i otevřeně (a na začátku) přiznat (ne to prezentovat jako normální knihovnu, kterou by nedejbože někdo měl používat)."
JJ, to je asi ta největší chyba v této knihovně.
blizz:
open System//univerzalna funkcia na prevod lubovolnych znakov
let replace src dst text =
let mask = Map(src |> Seq.mapi(fun i e -> e, i))
String.Join("", text |> Seq.map(fun c -> (dst : string).[mask.[c]]))
// fucia na prevod konkretnych znakov
let elscr = replace "+ůěľščřťžýáíé" "1122345567890"
"čřťžý" |> elscr
Diskuse je zrušena z důvodu spamu.
© 2005-2024 