성능을 고려하여 설계된 효율적이고 유연한 알고리즘의 정교하게 선별된 세트를 제공하는 플러터/다트 패키지입니다. 수학적으로 집중적인 또는 텍스트 처리 애플리케이션을 개발하는 개발자에게 이상적입니다. 주요 모든 플랫폼에서 최적화되어 일관된 동작과 속도를 보장합니다. 깔끔하고 잘 문서화된 코드로 간단한 사용 사례부터 복잡한 알고리즘 요구까지 모두 지원합니다.
사용 사례
데이터 정렬 및 검색
텍스트 패턴 매칭
수학 계산
최적화 문제
구조화된 데이터 파싱
알고리즘 프로토타이핑
주요 기능
고성능 구현
크로스 플랫폼 호환성
모듈형이고 확장 가능한 설계
잘 문서화된 API
유연성과 효율성에 초점을 맞추기
다양한 알고리즘 유형 지원
적합한 대상
빠른 알고리즘을 필요로 하는 개발자
수학 및 데이터 처리 애플리케이션
텍스트 분석 도구
교육 프로젝트
성능 중심 애플리케이션
고려 사항
알고리즘 개념을 이해해야 합니다
완전한 기능을 위해 추가 종속성이 필요할 수 있습니다
비트리비얼 계산 작업에 가장 적합
기본적인 유틸리티 함수에만 사용되지 않음
원본 README
연결된 소스 저장소의 README 원문 스냅샷입니다. 최신 내용은 저장소에서 확인하세요.
algorithmic
A collection of useful algorithms keeping performance and flexibility on mind.
Usage
The following import will give you access to all the algorithms in this package.
You can check the benchmark.log file for the benchmark results.
Searching algorithms
Index searching algorithms attempt to find the index of an item from a list.
Binary Search
⭐ 1000% faster than collection.lowerBound() and collection.binarySearch()
A faster searching algorithm for sorted list of items. It divides the list into two parts and discard one based on the middle value of them. This requires the list to be sorted in an increasing order.
Functions
Performance
Tests
Benchmark
Since
lowerBound()
O(logn)
✔️
✔️
0.0.3
upperBound()
O(logn)
✔️
✔️
0.0.3
binarySearch()
O(logn)
✔️
✔️
0.0.3
binarySearchUpper()
O(logn)
✔️
✔️
0.0.6
binarySearchQuick()
O(logn)
✔️
✔️
0.0.6
Linear Search
A general searching algorithm for any kind of list. It tests every elements on the list one by one.
Functions
Performance
Tests
Benchmark
Since
linearSearch()
O(n)
✔️
✔️
0.0.1
linearSearchBy()
O(n)
✔️
✔️
0.0.4
linearSearchReversed()
O(n)
✔️
✔️
0.0.1
linearSearchReversedBy()
O(n)
✔️
✔️
0.0.4
NOTE:
Sorting algorithms
Sorting algorithms puts a list of items into an increasing order.
Quick Sort
⭐ 500% faster than list.sort() for 700k items [algorithmic.quickSortHaore()]
Quicksort is an in-place sorting algorithm that works by selecting a pivot element and partitioning the list surrounding it. There are several schemes for selecting the pivot. The sorting performance varies for different schemes.
Functions
Performance
Tests
Benchmark
Since
quickSortHaore()
O(nlogn)
✔️
✔️
0.0.7
quickSortLomuto()
O(nlogn)
✔️
✔️
0.0.6
Counting Sort
⭐ 600% faster than list.sort() for 700k numbers
Counting sort is a specialized sorting algorithm to sort integers of ranges in linear time. It counts the frequencies of the numbers appearing in an array, and uses it to reconstruct a sorted list.
Functions
Performance
Tests
Benchmark
Since
countingSort()
O(n + k)
✔️
✔️
0.0.9
countingSortOf()
O(n + k)
✔️
✔️
0.0.9
Here, k is the range of numbers
Cocktail Shaker Sort
⭐ 400% faster than list.sort() for 32 items
Cocktail shaker sort extends bubble sort by operating in two directions. It has O(n) time complexity for an already sorted list.
This algorithm is known by many other names, e.g.: bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, shuttle sort etc.
Functions
Performance
Tests
Benchmark
Since
cocktailShakerSort()
O(n²)
✔️
✔️
0.0.8
Insertion Sort
⭐ 300% faster than list.sort() for 32 items
Insertion sort sorts splits the list into two parts: the left part is ordered and the right part is unordered. In each iteration, it removes the first item from right part, and insert it into the left part maintaining the increasing order.
Functions
Performance
Tests
Benchmark
Since
insertionSort()
O(n²)
✔️
✔️
0.0.5
Comb Sort
Comb sort improves bubble sort by eliminating small values near the end of the list, since they slows down bubble sort. It has O(n) time complexity for an already sorted list.
Functions
Performance
Tests
Benchmark
Since
combSort()
O(n²)
✔️
✔️
0.0.8
Selection Sort
Selection sort algorithm performs sorting by finding the minimum element from the unordered range and putting it at the beginning in each iteration.
Functions
Performance
Tests
Benchmark
Since
selectionSort()
O(n²)
✔️
✔️
0.0.5
Bubble Sort
Bubble sort performs sorting by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order.
Functions
Performance
Tests
Benchmark
Since
bubbleSort()
O(n²)
✔️
✔️
0.0.5
Gnome Sort
⭐ 300% faster than list.sort() for 32 numbers
Gnome sort is a variation to the insertion sort which uses a much simpler implementation. It has O(n) time complexity for an already sorted list.
Functions
Performance
Tests
Benchmark
Since
gnomeSort()
O(n²)
✔️
✔️
0.0.5
Merge Sort
Merge sort is a divide and conquer based algorithm, which can handle very large arrays. Unlike quick sort, it promises O(n log n) performance in worst case and provides stable sort. But it requires equal amount of memory as the length of the array and the implementation runs slower compared than quick sort.
Functions
Performance
Tests
Benchmark
Since
mergeSort()
O(nlogn)
✔️
✔️
0.0.8
Radix Sort
⭐ 200% faster than list.sort() for 700k numbers
Radix sort can sort a range of integers without using any comparisons. It is a special form of bucket sort, which distribute elements into buckets according to their radix.
Functions
Performance
Tests
Benchmark
Since
radixSort()
O(nlog_bn)
✔️
✔️
0.0.9
radixSortOf()
O(nlog_bn)
✔️
✔️
0.0.9
Here, b is the radix
String Algorithms
String Metrics
Levenshtein Distance
⭐ 120% faster than edit_distance.Levenshtein().distance()
Levenshtein distance returns the minimum number of ediit operations to transform one string (or array) to another. The permitted operations here are insertion, deletion and substitution. The Levenshtein distance between ABCD and BED is 2.
Functions
Performance
Tests
Benchmark
Since
levenshteinDistance()
O(nm)
✔️
✔️
0.0.9
levenshteinDistanceOf()
O(nm)
✔️
✔️
0.0.9
Here, n and m are the length of first and second string respectively.
Damerau-Levenshtein Distance
⭐ 200% faster than edit_distance.Damerau().distance()
Damerau–Levenshtein distance is a variation of Lavenshtein distance which permits transposition of two adjacent characters along with insertion, deletion and substitution. e.g.: The Damerau-Levenshtein distance between CA and ABC is 2.
Functions
Performance
Tests
Benchmark
Since
damerauLevenshteinDistance()
O(nmlog k)
✔️
✔️
0.0.10
damerauLevenshteinDistanceOf()
O(nmlog k)
✔️
✔️
0.0.10
Here, n and m are the length of first and second string respectively and k is number of unique characters appearing in both string.
⭐ 1000% faster than edit_distance.Damerau().distance()
The Damerau–Levenshtein distance can be restricted with a condition that no substring can be edited more than once, which simplifies the implementation of transposition lookup. This distance is also known as Optimal String Alignment distance. e.g.: The restricted Damerau-Levenshtein edit distance between CA and ABC is 3.
Functions
Performance
Tests
Benchmark
Since
restrictedDamerauDistance()
O(nm)
✔️
✔️
0.0.10
restrictedDamerauDistanceOf()
O(nm)
✔️
✔️
0.0.10
Here, n and m are the length of first and second string respectively.
Jaro similarity & Jaro-Winkler distance
The Jaro similarity between two strings is the weighted sum of percentage of matched characters from each string and transposed characters. Winkler increased this measure for matching initial characters.
Functions
Performance
Tests
Benchmark
Since
jaroSimilarity()
O(nm)
✔️
✔️
0.0.10
jaroSimilarityOf()
O(nm)
✔️
✔️
0.0.10
jaroWinklerSimilarity()
O(nm)
✔️
✔️
0.0.10
jaroWinklerSimilarityOf()
O(nm)
✔️
✔️
0.0.10
Here, n and m are the length of first and second string respectively.
Hamming Distance
Hamming distance between two equal-length strings is the number of positions at which the characters differs. In this implementation, if two strings are not equal, the shorter string is padded to match the longer ones.
Functions
Performance
Tests
Benchmark
Since
hammingDistance()
O(n)
✔️
➖
0.0.10
hammingDistanceOf()
O(n)
✔️
➖
0.0.10
Lee Distance
Lee distance can only be calculated between two equal-length strings.
Functions
Performance
Tests
Benchmark
Since
leeDistance()
O(n)
✔️
➖
0.0.10
leeDistanceOf()
O(n)
✔️
➖
0.0.10
Longest Common Subsequence Length
⭐ 200% faster than edit_distance.LongestCommonSubsequence().distance()
Longest common substrings and longest common subsequences are not the same. Unlike substrings, subsequences are not required to occupy consecutive positions.
Functions
Performance
Tests
Benchmark
Since
longestCommonSubsequenceLength()
O(nm)
✔️
✔️
0.0.10
longestCommonSubsequenceLengthOf()
O(nm)
✔️
✔️
0.0.10
Here, n and m are the length of first and second string respectively.
Jaccard index / Tanimoto coefficient
⭐ 150% faster than edit_distance.LongestCommonSubsequence().distance()
Jaccard index is a metric used to measure similarity of two samples sets.
The complement of it is Jaccard distance which measures the total number of items that is present in one list but not the other.