Jak szybki jest Data.Array?

Question

documentation z Data.Array brzmi:

Haskell zapewnia wieloostrzowych tablic, które mogą być traktowane jako funkcji, których domeny są izomorficzne do sąsiadujących podzbiorów całkowitymi. Funkcje ograniczone w ten sposób można skutecznie zrealizować w postaci ; w szczególności programista może rozsądnie spodziewać się szybkiego dostępu do komponentów.

Zastanawiam się, jak szybko mogą być (!) i (//). Czy mogę oczekiwać od nich złożoności O (1), jak bym od ich imperatywnych odpowiedników?

Answer 1

Ogólnie, tak, powinieneś być w stanie oczekiwać O (1) od !, chociaż nie jestem pewien, czy jest to zagwarantowane przez standard.

Możesz chcieć zobaczyć pakiet wektorowy, jeśli chcesz mieć szybsze tablice (za pomocą fuzji strumieniowej). Jest również lepiej zaprojektowany.

Należy pamiętać, że // jest prawdopodobnie O (n), chociaż musi przejść przez tę listę (tak, jak zrobiłby to imperatywny program). Jeśli potrzebujesz dużo mutacji, możesz użyć MArray lub MVector.