Метод скользящего окна: Обработка текстовых данных из сети "на лету"

Здравствуйте, уважаемые.

Сегодня я хотел бы затронуть проблему, которую вчера решил в сообщесте программистов Подведу итоги.

Красиво назвал тему: "Метод скользящего окна". Да, этот термин я услышал, учась в университете. Надо же! Университет мне что-то дал.
Задача: обработка данных по мере их поступления через низкоскоростную сеть. Необходимо извлечь из страницы список элементов (это может быть таблица телефонных номеров, таблица тем на форуме, таблица чего угодно)
И здесь нам поможет как раз это метод скользящего окна. Для того, кто не смотрел по приведенной ссылке, смысл его заключается в том, что мы знаем наверняка максимальный размер куска текста, который бы мы могли бы распознать и извлечь из него данные. К примеру, он равен N. В таком случае буффер данных, или, как мы выразились, "окно", будет давать нам представление не обо всём тексте, а только о той, части которая в него загружена. Это дает нам возможность обработать данные не дожидаясь полной загрузки текста.

Какого же размера может быть окно? Можно с этим поэксперементировать, но минимальный размер окна должен быть равен 2N(*** поправка в комментарии). Почему? Да потому что если взять, к прмеру N или 1.5*N, то у нас может произойти такая ситуация, когда окно видит макушку нужной записи, после скольжения в пол-окна, мы можем просто напросто уже видеть только заднюю часть этой записи. Очень некрасиво :(
Согласен с тем, что можно скользить окном помаленьку на 1 символ, но это очень трудоемко и неэффективно. В этом алгоритме лучше прыгать сразу на N символов, это позволит нам быстро проходить участки, где нет ни одной нужной нам записи.
Чем больше размер экрана (окна), тем меньше работы с памятью и строками нам предстоит, но окно всегда надо сдвигать не более чем на (k - 1)N, где k коэффиицент размера окна и k > 1. kN - размер окна.

Вот приблизительный код:

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class ScreenSlide {
    private static Pattern PATTERN = Pattern.compile("<tr><td>(.+)</td></tr>");
    private static int MAX_TEMPLATE_SIZE = 125;
 private static int K = 2;
 public static void main(String[] args) throws IOException {
        InputStreamReader reader = new InputStreamReader(new FileInputStream("c:/www/home/htdocs/11.txt"), "CP1251");
        char[] buffer = new char[K*MAX_TEMPLATE_SIZE];
        int shift = buffer.length;
        int am;
        while ((am = read(reader, buffer, buffer.length - shift)) != -1) {
            String s = new String(buffer, 0, am + buffer.length - shift);
            Matcher m = PATTERN.matcher(s);
   boolean found = false;
   while (m.find()) {
                // Нашли, сдвигаем в конец найденого
                System.out.println(m.group());
                shift = m.end();
    found = true;
   }
            if (!found) {
                // не нашли, значит смело можем двигать на (k - 1)N
                shift = (K-1)*MAX_TEMPLATE_SIZE;
            }
            // Сдвигаем неотработанную часть массива в начало
            System.arraycopy(buffer, shift, buffer, 0, buffer.length - shift);
        }
    }

 /*
  * Гарантированно заполняем до конца буффера или до конца потока
  */
 private static int read(InputStreamReader reader, char[] buffer, int offset) throws IOException {
  int total = offset;
  int am;
  while (total < buffer.length && (am = reader.read(buffer, total, buffer.length - total)) != -1)
   total += am;
  if (total == offset)
   return -1;
  return total - offset;
 }
}

Текст файла:

wef wkejfwae
fwaefkj waklgrjaewr
gergkl;j esklrgjerg
ergj eslkrgjserg
ergekls;jr gklesjrg
e
<table>
<tr><td>Первая строка</td></tr>
<tr><td>Вторая строка</td></tr>
<tr><td>Третья строка</td></tr>
<tr><td>Четвертая ооооооооооооооочень длинная строка</td></tr>
<tr><td>Пятая строчка</td></tr>
<tr><td>Шестая строчка</td></tr>
<tr><td>Достала меня эта экранная функция</td></tr>
</table>

Сравнивал с полной загрузкой страницы:

Time for screen string: 1062 ms
Time for screen string: 828 ms
Time for screen string: 828 ms
Time for screen string: 782 ms
Time for screen string: 813 ms
Time for screen string: 797 ms
Time for screen string: 812 ms
Time for screen string: 765 ms
Time for screen string: 781 ms
Time for screen string: 782 ms
AVG for screen string: 825 ms
Time for simple string: 875 ms
Time for simple string: 796 ms
Time for simple string: 688 ms
Time for simple string: 750 ms
Time for simple string: 734 ms
Time for simple string: 703 ms
Time for simple string: 719 ms
Time for simple string: 688 ms
Time for simple string: 703 ms
Time for simple string: 734 ms
AVG for simple string: 739 ms

Более менее сносное 14 %
Смотрим, рецензируем, пользуемся.