Как определить самую длинную увеличивающуюся подпоследовательность с помощью динамического программирования?
Вы получаете ошибку, потому что ваш WASM имеет операторы импорта, в то время как ваш вызов instantiateStreaming не отправляет importObject.
Но основной способ использования WASM из Javascript намного проще, чем: просто определите функцию в WASM, которую вы можете вызывать из JS, а затем, например, выполните «выборку» из JS («add.wasm») :
(module
(type $t0 (func (param i32 i32) (result i32)))
(func $add (type $t0) (param $p0 i32) (param $p1 i32) (result i32)
get_local $p0
get_local $p1
i32.add)
(export "add" (func $add)))
А затем вызвать его из Javascript:
const wasmInstanceFromFile = await WebAssembly.instantiateStreaming(await fetch('add.wasm'));
let sum = wasmInstanceFromFile.instance.exports.add(1,2);
3 ответа
Хорошо, сначала я опишу простейшее решение, которое является O(N^2), где N - размер коллекции. Существует также решение O(N log N), которое я также опишу. Ищите его здесь в разделе Эффективные алгоритмы.
Я буду считать, что индексы массива от 0 до N - 1. Поэтому определим DP[i] как длину LIS (Longest increasing subsequence), которая заканчивается на элементе с индексом i. Для вычисления DP[i] мы просматриваем все индексы j < i и проверяем, если DP[j] + 1 > DP[i] и array[j] < array[i] (мы хотим, чтобы он увеличивался). Если это так, то мы можем обновить текущий оптимум для DP[i]. Чтобы найти глобальный оптимум для массива, можно взять максимальное значение из DP[0...N - 1].
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
Я использую массив prev, чтобы иметь возможность позже найти фактическую последовательность, а не только ее длину. Просто рекурсивно возвращайтесь назад от bestEnd в цикле, используя prev[bestEnd]. Значение -1 является знаком остановки.
Хорошо, теперь перейдем к более эффективному O(N log N) решению:
Пусть S[pos] определяется как наименьшее целое число, которое завершает возрастающую последовательность длины pos. Теперь пройдитесь по каждому целому числу X входного множества и сделайте следующее:
Если
X> последнего элемента вS, то добавьтеXв конецS. Это означает, что мы нашли новый наибольшийLIS.Иначе найдем наименьший элемент в
S, который>=, чемX, и изменим его наX. ПосколькуSотсортирован в любой момент времени, элемент может быть найден с помощью двоичного поиска заlog(N).
Общее время выполнения - N целых чисел и бинарный поиск для каждого из них - N * log(N) = O(N log N)
Теперь давайте рассмотрим реальный пример:
Коллекция целых чисел:
2 6 3 4 1 2 9 5 8
Шаги:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
Итак, длина БИС составляет 5 (размер S).
Для восстановления фактической LIS мы снова воспользуемся родительским массивом.
Пусть parent[i] - предшественник элемента с индексом i в LIS, заканчивающийся на элементе с индексом i.
Чтобы упростить задачу, мы можем хранить в массиве S не сами целые числа, а их индексы (позиции) в множестве. Мы не храним {1, 2, 4, 5, 8}, а храним {4, 5, 3, 7, 8}.
То есть input[4] = 1, input[5] = 2, input[3] = 4, input[7] = 5, input[8] = 8.
Если мы правильно обновим родительский массив, то LIS будет выглядеть так:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
Теперь перейдем к главному - как обновить родительский массив? Есть два варианта:
Если
X> последнего элемента вS, тоparent[indexX] = indexLastElement. Это означает, что родителем самого нового элемента является последний элемент. Мы просто добавляемXв конецS.Иначе находим индекс наименьшего элемента в
S, который>=, чемX, и меняем его наX. Здесьparent[indexX] = S[index - 1].
Вот мое решение Leetcode с использованием бинарного поиска: ->
class Solution:
def binary_search(self,s,x):
low=0
high=len(s)-1
flag=1
while low<=high:
mid=(high+low)//2
if s[mid]==x:
flag=0
break
elif s[mid]<x:
low=mid+1
else:
high=mid-1
if flag:
s[low]=x
return s
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
s=[]
s.append(nums[0])
for i in range(1,len(nums)):
if s[-1]<nums[i]:
s.append(nums[i])
else:
s=self.binary_search(s,nums[i])
return len(s)
Простейшее решение LIS в C ++ с O (nlog (n)) сложностью по времени
#include <iostream>
#include "vector"
using namespace std;
// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
if(beg<=end)
{
int mid = (beg+end)/2;
if(a[mid] == value)
return mid;
else if(value < a[mid])
return ceilBinarySearch(a,beg,mid-1,value);
else
return ceilBinarySearch(a,mid+1,end,value);
return 0;
}
return beg;
}
int lis(vector<int> arr)
{
vector<int> dp(arr.size(),0);
int len = 0;
for(int i = 0;i<arr.size();i++)
{
int j = ceilBinarySearch(dp,0,len-1,arr[i]);
dp[j] = arr[i];
if(j == len)
len++;
}
return len;
}
int main()
{
vector<int> arr {2, 5,-1,0,6,1,2};
cout<<lis(arr);
return 0;
}
ВЫХОД:
4