środa, 21 grudnia 2011

#next na każdym znaku Stringa

Jakiś czas temu deliberowaliśmy ( :] ) na forum jak najszybciej i najbardziej elegancko rozwiązać wywołanie #next na każdym znaku Stringa. Jeżeli ktoś nie wie jak działa String#next:


Niestety jeżeli wywołamy #next na ciągu znaków nie zadziała tak jakbyśmy chcieli:


Można to rozwiązać na różne sposoby - od zmiany w miejscu poprzez #next! w pętli, stworzenie nowego stringa w #each_char, podzielenie na tablicę i wykonanie #next na każdym elemencie a na końcu #join na tablicy. Jedne rozwiązania są mniej lub bardziej eleganckie (oraz mniej lub bardziej wydajne). Najszybsze  (i jednocześnie najkrótsze) okazało się wykorzystanie wyrażeń regularnych. Poniżej benchmark kilku rozwiązań ze wspomnianego tematu*:

#each_char_next wykonuje się tylko dla n == 1000. Dla wyższych wykonywał się tragicznie długo.


Oraz wyniki:
MRI 1.9.2


JRuby 1.6.5 (w trybie zgodności z ruby-1.9.2-p136)


Różnica pomiędzy #gsub a #each_next! nie jest duża (aczkolwiek dla większych n była coraz wieksza), ale kod używający wyrażeń regularnych jest krótszy, czytelniejszy i bardziej RubyWay (brak zmiany stringa "w miejscu" itd.). Mówiąc szczerze nie wiem czemu gsub jest aż tak szybki. Może ktoś wie?



* komputer użyty w benchmarku:


Jak słusznie ktoś zauważył w komentarzach, należałoby dodać warming-up, żeby nie uruchamiać kodu "na zimno". Poniżej nowy kod oraz wyniki:

8 komentarzy:

  1. jaki był rehearsal dla tych testów ?

    OdpowiedzUsuń
  2. Chodzi Ci o liczbę powtórzeń benchmarka? Jak to #bmbm - 2 powtórzenia. To nie miał być jakiś hiper-ekstra benchmark na 1000 powtórzeń i uśredniennie wyniku ;)

    Chodziło o sprawdzenie które rozwiązanie jest **mniej więcej** najszybsze.

    OdpowiedzUsuń
  3. w takim razie uruchamiasz kod zimny który może być 10-50x wolniejszy niż w rzeczywistych warunkach po rozgrzaniu

    OdpowiedzUsuń
  4. Ok, dodałem warm up. Czasy rzeczywiście trochę się zmieniły (na MRI na 2-gie miejsce wysunął się split_map_join ;)) ale najszybszy jest i tak gsub

    link - https://gist.github.com/1512039

    OdpowiedzUsuń
  5. O co chodzi z tym randem tam ? Wiesz w ogóle co to jest rozgrzewanie ?

    OdpowiedzUsuń
  6. Poki co to nie jest bug

    OdpowiedzUsuń