Maximum subarray problem optimization for specific data

• Autorzy: Rojek T.

Identyfikatory

DOI

10.5604/01.3001.0010.7507

Warianty tytułu

PL

Optymalizacja problemu największej podtablicy dla specyficznych danych

• Języki publikacji: EN

Abstrakty

EN

The maximum subarray problem (MSP) is to the find maximum contiguous sum in an array. This paper describes a method of Kadanes algorithm (the state of the art) optimization for specific data (continuous sequences of zeros or negative real numbers). When the data are unfavourable, the modification of the algorithm causes a non significant performance loss (1% > decrease in performance). The modification does not improve time complexity but reduces the number of elementary operations. Various experimental data sets have been used to evaluate possible time efficiency improvement. For the most favourable data sets an increase in efficiency of 25% can be achieved.

PL

Problem najwiekszej podtablicy to inaczej znalezienie podciągu, którego suma na największą wartość. Artykuł opisuje optymalizację algorytmu Kadane dla specyficznych danych (z powtarzającymi się ciągami zer lub liczb negatywnych). W przypadku niekorzystnych danych wejściowych zaproponowa modyfikacja nieznacznie spowalnia działanie algorytmu (mniej niż 1% szybkości działania). Ulepszenie algorytmu nie zmienia rzędu asymptotycznego tempa wzrostu, lecz zmniejsza ilość elementarnych operacji. Eksperymenty wykazały, że dla sprzyjających danych możemy zmniejszyć efektywny czas działania algorytmu o 25%.

Słowa kluczowe

EN

algorithm design and analysis; maximum subarray problem; Kadane’s algorithm; optimization

PL

analiza algorytmów; projektowanie algorytmów; problem maksymalnej podtablicy; algorytm Kadane; optymalizacja

• Wydawca: Wydawnictwo Politechniki Lubelskiej
• Czasopismo: Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska
• Rocznik: 2017
• Tom: T. 7, nr 4
• Strony: 62--65
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Rojek T.

• Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics

Bibliografia

• [1] Lloyd A.: Longest biased interval and longest non-negative sum interval. Bioinformatics 19, 2003, 1294–1295.
• [2] Bae Sung Eun: Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Ph.D. Thesis, University of Canterbury, 2007.
• [3] Bentley J.: Programming pearls: algorithm design techniques. Communications of the ACM, 27(9), 1984, 865–873.
• [4] BT Series Broadcasting. Parameter values for the HDTV standards for production and international programme exchange BT Series Broadcasting service – volume 5, 2002.
• [5] Grenander U.: Pattern analysis. Springer, 1978.
• [6] Huang X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Computer applications in the biosciences: CABIOS 10, 1994, 219–225.
• [7] Larson R. C., Odoni A. R.: Urban operations research. Prentice-Hall, New Jersey 1981.
• [8] Lin Yaw Ling, Jiang Tao, Chao Kun Mao: Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. Journal of Computer and System Sciences 65, 2003, 570–586.
• [9] Perumalla K., Deo N.: Parallel algorithms for maximum subsequence and maximum subarray. Parallel Processing Letters 5(03), 1995, 367–373.
• [10] Tokyo IBM: Data Association Mining Rules: Using Algorithms, Optimized and Scheme, Visualization, 1996.
• [11] Wang L., Xu Ying: SEGID: Identifying interesting segments in (multiple) sequence alignments. Bioinformatics 19, 297–298, 2003.