| dbo:abstract
|
- La transformada schwartziana és una tècnica en programació que s'utilitza per a l'ordenació eficient d'una . Aquesta fa servir el resultat d'una operació de càlcul intensiu sense la necessitat d'efectuar-la per a cada comparació que fa la subrutina de comparació. Aquesta pràctica rep el nom de , qui va popularitzar-la entre els programadors de Perl. No obstant això, s'ha utilitzat en informàtica com a mínim des de l'estàndard . És un cas especial de memoització, que funcionaria per a qualsevol algorisme. Per exemple, per a ordernar una llista de fitxers d'acord amb el seu moment de modificació, sense transformada seria (en pseudocodi): funció ComparacióIngènua(fitxer a, fitxer b) {retorna TempsModificació(a) < TempsModificació(b)}// S'assumeix que ordena(llista, PredicatComparació) ordena la llista fent servir// el PredicatComparació per a comparar dos elements.MatriuOrdenada := ordena(MatriuFitxers, ComparacióIngènua) A menys que els temps de modificació es memoritzin per a cada fitxer, aquest mètode requereix tornar a calcular cada vegada que un fitxer es compara en l'ordenació.Com a alternativa, amb la transformada schwartziana: per cada fitxer a MatriuFitxersinserta Matrix(fitxer, TempsModificació(fitxer)) al final de MatriuTransformadafunció ComparacióSimple(matriu a, matriu b) {retorna a[2] < b[2]}MatriuTransformada := ordena(MatriuTransformada, ComparacióSimple)per cada fitxer a MatriuTransformadainserta MatriuTransformada[1] al final MatriuOrdenada Primer el bucle inicial itera cada element de MatriuFitxers i crea una referència d'una matriu anònima per a cada un. La matriu anònima té doncs dos elements: l'original de MatriuFitxers i el temps de modificació d'aqueix fitxer. A continuació s'ordena la llista de referències de matrius anònimes que retorna el primer mapatge. La llista s'ordena d'acord amb els segons elements de cada matriu anònima. Finalment la llista ordenada de referències de matrius s'itera en el darrer bucle. Aquest simplement construeix la matriu ordenada a partir del primer element de cada referència de les matrius, que és de fet el nom del fitxer. (ca)
- In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom is appropriate for comparison-based sorting when the ordering is actually based on the ordering of a certain property (the key) of the elements, where computing that property is an intensive operation that should be performed a minimal number of times. The Schwartzian transform is notable in that it does not use named temporary arrays. The Schwartzian transform is a version of a Lisp idiom known as decorate-sort-undecorate, which avoids recomputing the sort keys by temporarily associating them with the input items. This approach is similar to memoization, which avoids repeating the calculation of the key corresponding to a specific input value. By comparison, this idiom assures that each input item's key is calculated exactly once, which may still result in repeating some calculations if the input data contains duplicate items. The idiom is named after Randal L. Schwartz, who first demonstrated it in Perl shortly after the release of Perl 5 in 1994. The term "Schwartzian transform" applied solely to Perl programming for a number of years, but it has later been adopted by some users of other languages, such as Python, to refer to similar idioms in those languages. However, the algorithm was already in use in other languages (under no specific name) before it was popularized among the Perl community in the form of that particular idiom by Schwartz. The term "Schwartzian transform" indicates a specific idiom, and not the algorithm in general. For example, to sort the word list ("aaaa","a","aa") according to word length: first build the list (["aaaa",4],["a",1],["aa",2]), then sort it according to the numeric values getting (["a",1],["aa",2],["aaaa",4]), then strip off the numbers and you get ("a","aa","aaaa"). That was the algorithm in general, so it does not count as a transform. To make it a true Schwartzian transform, it would be done in Perl like this: @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] } # Use numeric comparison, fall back to string sort on original map { [$_, length($_)] } # Calculate the length of the string @unsorted; (en)
- シュワルツ変換（シュワルツへんかん、英: schwartzian transform）は、リストの要素のソートを効率良く行うためのプログラミングの手法の一つである。このイディオム は、要素の順序が実際には要素のあるプロパティ（キー）の順序に基づいていて、キーの計算に多くの計算資源を要するため計算回数を最小限にしたい状況で行う比較ソートに適している。シュワルツ変換の特徴として、名前付きの一時配列を使わないことが挙げられる。 シュワルツ変換は LISP において decorate-sort-undecorate（DSU）として知られるイディオムの一種であり、一時的に入力要素とキーを関連付けることでキーの再計算を避けるイディオムである。このアプローチはメモ化に似ていて、メモ化では特定の入力値に関連しているキーの再計算を避けている。比較すると、シュワルツ変換は各入力要素のキーを計算回数が厳密に一度であることを保証する。ただし、入力要素に重複がある場合、同値な要素に対して複数回キーの計算を行う。 シュワルツ変換の名はランダル・L・シュワルツ（Randal L. Schwartz）に因む。シュワルツは Perl 5 リリース直後の1994年にこのイディオムを Perl で初めて実装した。「シュワルツ変換」の語は専ら Perl の文脈でのみ用いられてきたが、後に Python など他のプログラミング言語のユーザの間でも、類似のイディオムに言及する際に用いられるようになった。しかしこのアルゴリズムは、シュワルツによる特定のイディオムとして Perl コミュニティの間で普及するより以前に、既に他の言語で（特定の名前を与えられずに）用いられている。「シュワルツ変換」の語は特定のイディオムを示すのであって、一般のアルゴリズムを示すのではない。 例として、リスト ("aaaa","a","aa") を各語の長さに基づいて並び替えることを考える。まず文字列と長さの配列からリスト (["aaaa",4],["a",1],["aa",2]) を生成し（decorate）、次にタプルの数値に基づいてこのリストをソートし (["a",1],["aa",2],["aaaa",4]) を得て（sort）、最後にソート済みリスト要素から数値を取り除き（undecorate）、目的のリスト ("a","aa","aaaa") を得る。このアルゴリズムの Perl での実装を以下に示す： @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] } # 先に長さを比較し、長さの等しい場合のみ文字列の比較を行う map { [$_, length($_)] } # 文字列の長さを計算する @unsorted; (ja)
- Transformacja Schwartza (ang. Schwartzian Transform) – idiom programistyczny wykorzystywany w informatyce do zwiększenia wydajności procesu sortowania listy elementów. Idiom ten jest odpowiedni do sortowania opartego na porównywaniu elementów listy, gdy porządkowanie listy odbywa się w oparciu o pewną właściwość (klucz) sortowanych elementów, a obliczanie tej właściwości jest mocno obciążające dla komputera, stąd operacja obliczania wartości klucza powinna być wykonywana minimalną liczbę razy. Wyróżniającą cechą Transformacji Schwartza jest to, że nie używa ona nazwanych tablic tymczasowych. Idiom ten został nazwany od jego twórcy i popularyzatora – Randala L. Schwartza, który jako pierwszy, w grudniu 1994 r., niedługo po ukazaniu się języka programowania Perl w wersji 5. na grupie dyskusyjnej Usenet zademonstrował jego użycie. Nazwa „Transformacja Schwartza” od momentu jej powstania przez wiele lat stosowana była wyłącznie w odniesieniu do języka programowania Perl, później jednak została przyjęta również w innych językach, takich jak np. Python w odniesieniu do podobnych idiomów programistycznych stosowanych przez ich użytkowników. Termin „Transformacja Schwartza” wskazuje konkretny idiom, a nie algorytm w ogólności. Transformacja Schwartza jest wersją idiomu z języka programowania Lisp znanego jako decorate-sort-undecorate, który unika ponownego obliczania kluczy sortujących przez tymczasowe kojarzenie ich z elementami wejściowymi. Podstawową ideą transformacji Schwartza jest: weź listę do posortowania i utwórz drugą, tymczasową listę zawierającą zarówno wartość oryginalną, jak i wartość transformowaną – element używany do właściwego sortowania. Po posortowaniu, element tymczasowy zostaje usunięty, pozostawiając posortowaną listę z elementami z oryginalnej, wyjściowej listy. Przykład 1. Zakładając, że lista słów następującej postaci ("aaaa", "a", "aa") powinna zostać posortowana według długości słowa, w pierwszym kroku należy zbudować nową, tymczasową listę (["aaaa",4], ["a",1], ["aa",2]), następnie tak utworzoną listę należy posortować zgodnie z wartością numeryczną (klucz) odpowiadającą długości słowa, tak że powstała po sortowaniu lista przyjmie postać (["a",1], ["aa",2], ["aaaa",4]). Po usunięciu liczb otrzymuje się ostatecznie posortowaną listę zgodnie z długością słów w niej występujących ("a", "aa", "aaaa"). Aby ten ogólny algorytm przedstawić w Perlu jako transformację Schwartza należy napisać poniższy kod: @sorted = map { $_->[0] } # wyodrębnienie oryginalnych elementów listy sort { $a->[1] <=> $b->[1] } # porównanie numeryczne po kluczu map { [$_, length($_)] } # obliczenie długości łańcucha (wyrazu) @unsorted;Przykład 2. Należy posortować pliki w danym katalogu według rozmiaru od wartości największej do najmniejszej. Jedną z metod w języku programowania Perl jest poniższy kod. opendir(my $dh, '.') || die;@names = readdir $dh;@sorted_files = sort { -s $b <=> -s $a } @names; Ten najprostszy sposób posiada jednocześnie największą wadę tego rozwiązania – sprawdzanie rozmiaru każdego pliku wykonywane jest wiele razy, co przy dużej ilości plików może mieć niekorzystny wpływ na wydajność systemu dyskowego i operacji wejścia-wyjścia. Średnia złożoność obliczeniowa funkcji sort w tej metodzie sortowania jest rzędu O(n log n), w najgorszym przypadku O(n2). Zatem sposób ten jest efektywny dla elementów o niewielkiej liczebności. Pewnym rozwiązaniem tego problemu jest wykonanie obliczenia rozmiarów plików przed wykonaniem sortowania. W takim przypadku należy użyć dodatkowej tablicy do przechowania obliczonych wyników. @temp = map { [$_, -s $_] } @names;@sorted_files = sort { $b->[1] <=> $a->[1] } @temp; Zastosowanie permanentnej tablicy @temp powoduje zajęcie pewnego obszaru w pamięci operacyjnej w trakcie działania całego programu. Dodatkowo, jeżeli użytkownik zamiast sortowania po rozmiarze pliku potrzebować będzie listy plików posortowanych według daty ostatniej modyfikacji, potrzebne będzie utworzenie nowej struktury tablicowej. Aby rozwiązać powyższe problemy należy zastosować transformację Schwartza, wykorzystując poniższy kod. @sorted_names = map { $_->[0] } # wyodrębnienie oryginalnej listy sort { $b->[1] <=> $a->[1] } # sortowanie (w odwrotnej kolejności) map { [ $_, -s $_ ] } # obliczanie rozmiaru pliku @names; (pl)
- Преобразова́ние Шва́рца — идиома, появившаяся в языке программирования Perl, которая решает задачу эффективной сортировки списков элементов по сложным (вычисляемым) атрибутам. Идея состоит в том, чтобы сравниваемые вычисляемые атрибуты элементов (например, длина строки, часть строки, квадрат числа, прочие формулы и внешние запросы) вычислить один раз для всех элементов и занести во временный массив, который затем сортируется стандартной функцией сортировки по этим результатам, после чего временные данные отбрасываются. По сути, это кэширование (временное запоминание) вычисляемых атрибутов, поскольку в процессе сортировки они используются многократно (при сравнениях элементов). В языке Perl, благодаря использованию «переменной по умолчанию», этот алгоритм умещается в одно выражение из трёх функций, то есть очень кратко и наглядно. Идиома получила своё название в честь Рэндела Шварца, который продемонстрировал её спустя некоторое время после выхода Perl 5 в 1994 году. Термин «преобразование Шварца» долгие годы использовался исключительно для языка программирования Perl, но позже это преобразование было адаптировано другими программистами и для других языков (например, Python). Алгоритм, используемый в преобразовании Шварца, существовал в некоторых языках программирования (не имея специального названия) ещё до того, как он был популяризирован в сообществе Perl-программистов в качестве идиомы. (ru)
|
| rdfs:comment
|
- La transformada schwartziana és una tècnica en programació que s'utilitza per a l'ordenació eficient d'una . Aquesta fa servir el resultat d'una operació de càlcul intensiu sense la necessitat d'efectuar-la per a cada comparació que fa la subrutina de comparació. Aquesta pràctica rep el nom de , qui va popularitzar-la entre els programadors de Perl. No obstant això, s'ha utilitzat en informàtica com a mínim des de l'estàndard . És un cas especial de memoització, que funcionaria per a qualsevol algorisme. (ca)
- In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom is appropriate for comparison-based sorting when the ordering is actually based on the ordering of a certain property (the key) of the elements, where computing that property is an intensive operation that should be performed a minimal number of times. The Schwartzian transform is notable in that it does not use named temporary arrays. (en)
- シュワルツ変換（シュワルツへんかん、英: schwartzian transform）は、リストの要素のソートを効率良く行うためのプログラミングの手法の一つである。このイディオム は、要素の順序が実際には要素のあるプロパティ（キー）の順序に基づいていて、キーの計算に多くの計算資源を要するため計算回数を最小限にしたい状況で行う比較ソートに適している。シュワルツ変換の特徴として、名前付きの一時配列を使わないことが挙げられる。 シュワルツ変換は LISP において decorate-sort-undecorate（DSU）として知られるイディオムの一種であり、一時的に入力要素とキーを関連付けることでキーの再計算を避けるイディオムである。このアプローチはメモ化に似ていて、メモ化では特定の入力値に関連しているキーの再計算を避けている。比較すると、シュワルツ変換は各入力要素のキーを計算回数が厳密に一度であることを保証する。ただし、入力要素に重複がある場合、同値な要素に対して複数回キーの計算を行う。 (ja)
- Transformacja Schwartza (ang. Schwartzian Transform) – idiom programistyczny wykorzystywany w informatyce do zwiększenia wydajności procesu sortowania listy elementów. Idiom ten jest odpowiedni do sortowania opartego na porównywaniu elementów listy, gdy porządkowanie listy odbywa się w oparciu o pewną właściwość (klucz) sortowanych elementów, a obliczanie tej właściwości jest mocno obciążające dla komputera, stąd operacja obliczania wartości klucza powinna być wykonywana minimalną liczbę razy. Wyróżniającą cechą Transformacji Schwartza jest to, że nie używa ona nazwanych tablic tymczasowych. (pl)
- Преобразова́ние Шва́рца — идиома, появившаяся в языке программирования Perl, которая решает задачу эффективной сортировки списков элементов по сложным (вычисляемым) атрибутам. Идея состоит в том, чтобы сравниваемые вычисляемые атрибуты элементов (например, длина строки, часть строки, квадрат числа, прочие формулы и внешние запросы) вычислить один раз для всех элементов и занести во временный массив, который затем сортируется стандартной функцией сортировки по этим результатам, после чего временные данные отбрасываются. По сути, это кэширование (временное запоминание) вычисляемых атрибутов, поскольку в процессе сортировки они используются многократно (при сравнениях элементов). В языке Perl, благодаря использованию «переменной по умолчанию», этот алгоритм умещается в одно выражение из трёх (ru)
|
