Алгоритм оптимизации самой длинной общей подпоследовательности, написанный на PL / SQL - PullRequest
Новая
       6

Алгоритм оптимизации самой длинной общей подпоследовательности, написанный на PL / SQL

0 голосов
/ 09 января 2019

Я написал алгоритм самой длинной общей подпоследовательности в функции PL / SQL. Мне нужна только длина подпоследовательности в качестве вывода. Теперь моя самая большая проблема - это скорость функции при использовании этой функции для сотен тысяч записей. Существует вложенный цикл, который заполняет объект многомерного типа таблицы.

У меня есть две таблицы, одна из которых содержит 1 миллион записей (строка), а другая - почти 28 000 записей (строка). Требуется сопоставить каждую запись в таблице 1 с каждой записью таблицы 2 и получить длину LCS для каждой.

Согласно моему анализу, вложенный цикл занимает максимальное количество времени. 

/*
LCS LOGIC
*/

1 CREATE OR REPLACE
2  FUNCTION GET_LCS_LENGTH(    
3       table1_string  IN NVARCHAR2,
4       table2_string IN NVARCHAR2)
5     RETURN NUMBER
6   AS
7   TYPE t_number_array IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
8   TYPE t_bidimensional_number_array IS TABLE OF t_number_array INDEX BY BINARY_INTEGER;
9   matrix t_bidimensional_number_array ;
10    --...
11  BEGIN
12    len_str1     := LENGTH(table1_string);
13    len_str2     := LENGTH(table2_string);
14    matrix(1)(1) := 0;
15    FOR i IN 2..(len_str2+1)
16    LOOP
17      matrix(i)(1) := 0;
18      ch1          := SUBSTR(table2_string,i-1,1);
19      FOR j IN 2..(len_str1+1)
20      LOOP
21        matrix(1)(j)   := 0;
22        ch2            := SUBSTR(table1_string,j-1,1);
23        IF ch1          = ch2 THEN
24          matrix(i)(j) := matrix(i - 1)(j - 1) + 1;
25        ELSE
26          matrix(i)(j) := greatest(matrix(i)(j - 1),matrix(i - 1)(j));
27        END IF;
28      END LOOP;
29    END LOOP;
30    lcs_Dist := matrix(len_str2+1)(len_str1+1);
31    matrix.DELETE;
32  END;
  /*

  LCS LOGIC END

  */

Как я могу заменить этот вложенный цикл for, чтобы получить длину LCS или использовать другую логику, или как оптимизировать этот код дальше?

В настоящее время, когда одна запись в таблице 1 сопоставляется с каждыми 28 000 записей в таблице 2, это занимает 5 секунд, что обходится мне дорого.

Он должен работать за доли секунды для 28 000 записей, тогда только я смогу достичь определенной цели с другими 1 миллионами записей.

1 Ответ

0 голосов
/ 09 января 2019

Пара улучшений:

  • Вам не нужно хранить все строки матрицы, вам нужны только текущая строка и предыдущая строка.
  • Вам не нужно использовать ассоциативный массив (TABLE OF x INDEX BY y), и вы можете просто использовать коллекцию (TABLE OF x).
  • Вы можете отслеживать предыдущее значение в строке, чтобы вам не приходилось искать его в матрице каждую итерацию.

Что дает: 

CREATE FUNCTION get_lcs_length(
  in_str1 IN NVARCHAR2,
  in_str2 IN NVARCHAR2
) RETURN NUMBER
IS
  TYPE numbers_array IS TABLE OF NUMBER(4,0);
  TYPE matrix IS TABLE OF numbers_array;
  c_l1         CONSTANT NUMBER(4,0) := LENGTH( in_str1 );
  c_l2         CONSTANT NUMBER(4,0) := LENGTH( in_str2 );
  p_matrix              matrix;
  p_row                 NUMBER(1,0) := 1;
  p_prev_row            NUMBER(1,0) := 2;
  p_c1                  NCHAR(1);
  p_c2                  NCHAR(1);
  p_prev_value          NUMBER(4,0);
BEGIN
  IF in_str1 IS NULL OR in_str2 IS NULL THEN
    RETURN NULL;
  ELSIF c_l1 > c_l2 THEN
    RETURN get_lcs_length( in_str2, in_str1 );
  END IF;
  p_matrix := matrix( numbers_array(), numbers_array() );
  p_matrix(1).EXTEND( c_l1 );
  p_matrix(2).EXTEND( c_l1 );
  FOR x IN 1 .. c_l1 LOOP
    p_matrix(p_prev_row)(x) := 0;
  END LOOP;

  FOR y IN 1 .. c_l2 LOOP
    p_c2 := SUBSTR( in_str2, y, 1 );
    p_prev_value := 0;
    FOR x IN 1 .. c_l1 LOOP
      p_c1 := SUBSTR( in_str1, x, 1 );
      IF p_c1 = p_c2 THEN
        IF x = 1 OR y = 1 THEN
          p_prev_value := 1;
        ELSE
          p_prev_value := p_matrix(p_prev_row)(x-1) + 1;
        END IF;
        p_matrix(p_row)(x) := p_prev_value;
      ELSE
        p_prev_value := GREATEST( p_matrix(p_prev_row)(x), p_prev_value );
        p_matrix(p_row)(x) := p_prev_value;
      END IF;
    END LOOP;
    IF p_row = 1 THEN
      p_row      := 2;
      p_prev_row := 1;
    ELSE
      p_row      := 1;
      p_prev_row := 2;
    END IF;
  END LOOP;
  RETURN p_prev_value;
END get_lcs_length;
/
...