搜尋套件、儲存庫與 APP 分類

套件詳情v0.0.11

algorithmic

一組實用的演算法,同時考慮效能與彈性。

AndroidiOSWebmacOSWindowsLinux
近 30 天下載
5810
喜歡數
21
Pub 分數
160

安裝套件

flutter pub add algorithmic

套件介紹

根據套件公開資料產生的選型評估,僅供參考。

一個 Flutter/Dart 套件,提供經過精心挑選的高效且彈性演算法,專注於效能設計。它提供常用計算任務的可重複使用解決方案,非常適合從事數學密集或文字處理應用開發的開發者。該套件在所有主要平台皆經過優化,確保行為一致且快速。程式碼乾淨、文件完整,支援簡單使用情境與複雜演算法需求。

適用情境

  • 數據排序和搜索
  • 文字模式匹配
  • 數學計算
  • 優化問題
  • 解析結構化數據
  • 演算法原型設計

主要特色

  • 高效能實作
  • 跨平台相容性
  • 模組化且可擴充的設計
  • 文件完整的 API
  • 注重彈性與效率
  • 支援多種演算法類型

適合對象

  • 需要快速演算法的開發者
  • 數學與資料處理應用
  • 文字分析工具
  • 教育專案
  • 效能關鍵的應用程式

使用建議

  • 需要理解演算法概念
  • 可能需要額外的相依性才能實現完整功能
  • 最適合非複雜計算任務
  • 不適用於基本的實用函數

原始 README

以下為關聯原始碼儲存庫的 README 原文快照,最新內容請造訪原始碼儲存庫。

algorithmic

plugin version dependencies Dart

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.

import 'package:algorithmic/algorithmic.dart';

You can also import these algorithms separately:

Libraries Imported By
Search algorithms 'package:algorithmic/searching.dart'
Sort algorithms 'package:algorithmic/sorting.dart'
String algorithms 'package:algorithmic/string.dart'

Benchmarks

To run benchmark on your own machine:

$ dart run benchmark

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(log n) ✔️ ✔️ 0.0.3
upperBound() O(log n) ✔️ ✔️ 0.0.3
binarySearch() O(log n) ✔️ ✔️ 0.0.3
binarySearchUpper() O(log n) ✔️ ✔️ 0.0.6
binarySearchQuick() O(log n) ✔️ ✔️ 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(n log n) ✔️ ✔️ 0.0.7
quickSortLomuto() O(n log n) ✔️ ✔️ 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(n log n) ✔️ ✔️ 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(n log_b n) ✔️ ✔️ 0.0.9
radixSortOf() O(n log_b n) ✔️ ✔️ 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(n m) ✔️ ✔️ 0.0.9
levenshteinDistanceOf() O(n m) ✔️ ✔️ 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(n m log k) ✔️ ✔️ 0.0.10
damerauLevenshteinDistanceOf() O(n m log 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.

Restricted Damerau-Levenshtein Distance / Optimal String Alignment Distance

⭐ 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(n m) ✔️ ✔️ 0.0.10
restrictedDamerauDistanceOf() O(n m) ✔️ ✔️ 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(n m) ✔️ ✔️ 0.0.10
jaroSimilarityOf() O(n m) ✔️ ✔️ 0.0.10
jaroWinklerSimilarity() O(n m) ✔️ ✔️ 0.0.10
jaroWinklerSimilarityOf() O(n m) ✔️ ✔️ 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 Subsequence is the longest of the common subsequences of two strings.

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(n m) ✔️ ✔️ 0.0.10
longestCommonSubsequenceLengthOf() O(n m) ✔️ ✔️ 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.

Functions Performance Tests Benchmark Since
jaccardIndex() O(n log n) ✔️ ✔️ 0.0.10
jaccardIndexOf() O(n log n) ✔️ ✔️ 0.0.10
jaccardDistance() O(n log n) ✔️ ✔️ 0.0.10
jaccardDistanceOf() O(n log n) ✔️ ✔️ 0.0.10
Dice coefficient / Sørensen index

Sørensen–Dice coefficient is a metric used to measure similarity between two samples.

Functions Performance Tests Benchmark Since
diceIndex() O(n log n) ✔️ ✔️ 0.0.10
diceIndexOf() O(n log n) ✔️ ✔️ 0.0.10
Tversky Index

Tversky similarity index an asymmetric similarity measure between sets that compares a variant with a prototype.

Functions Performance Tests Benchmark Since
tverskyIndex() O(n log n) ✔️ ✔️ 0.0.10
tverskyIndexOf() O(n log n) ✔️ ✔️ 0.0.10

Links

所屬分類

原始碼儲存庫

使用此套件的專案