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

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

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

Красиво назвал тему: "Метод скользящего окна". Да, этот термин я услышал, учась в университете. Надо же! Университет мне что-то дал.
Задача: обработка данных по мере их поступления через низкоскоростную сеть. Необходимо извлечь из страницы список элементов (это может быть таблица телефонных номеров, таблица тем на форуме, таблица чего угодно)
И здесь нам поможет как раз это метод скользящего окна. Для того, кто не смотрел по приведенной ссылке, смысл его заключается в том, что мы знаем наверняка максимальный размер куска текста, который бы мы могли бы распознать и извлечь из него данные. К примеру, он равен 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 %
Смотрим, рецензируем, пользуемся.

Потоки: Мир захватили струйки информации!!!

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

Первой статьёй на новом месте хочу отметить новоселье.

Совсем недавно мне надо было обрабатывать информацию с сайта. Загружать страницы, извлекать из них список нужных записей. Я хотел бы сегодня уделить внимание важности потокового (имею ввиду не Thread, а Stream) подхода в любой задаче обработки данных.
Полная постановка задачи:
Из списка сайтов, на каждом информация расположена на нескольких страницах, необходимо извлечь ее и вывести пользователю.
Возможности системы: одновременная скачка страниц с разных сайтов.
Первоначально задача сходилась к тому, что у каждого сайта есть парсер, который последовательно обходит все нужные страницы, собирая информацию, после чего выдает результат запрашивающему.
Эти парсеры запускаются параллельно, т.е. разными потоками. Результаты работы потоков также складываются объединяются в список, он дальше выдается как результат.
Фактически трехзвенка.

Недостаток: надо ждать пока все данные будут готовы. Для этого может потребоваться достаточно времени, и мы можем потерять внимание пользователя.

Логичное решение этой ситуации — это выдавать результат постепенно, по мере готовности данных страницы от любого парсера. Если оставить всё как есть, то нам придется избавиться от класса, инкапсулирующего в себе параллельную обработку парсеров. Выпускать из ларца Пандоры
беды и горе — дело, конечно, смелое, но неблагоразумное.
На ум пришло кардинально изменить механизм обработки информации. Приходится вносить изменения в самый нижний уровень, а именно, в механизм обработки конкретной страницы. И вот он! Герой. Поток, во всём его величии и стати.
Алгоритм следующий: раньше мы добавляли данные в список и возращали его запрашивающему объекту, теперь мы не будем возвращать ничего, теперь мы будем писать в поток, предварительно благоразумно переданный обработчику страницы. Таким образом, теоретически, мы можем не дожидаться полной загрузки страницы, а обрабатывать содержимое по мере его поступления, если такое теоретически возможно, и сразу выплевывать извлеченную запись в поток.

Приблизительно это будет выглядеть так:

public class SitesCollectionHanlder {
 public void process(List<SiteHandler> handlers) {
  List<Thread> threads = new ArrayList<Thread>();
  for (final SiteHandler h : handlers) {
   Thread t = new Thread(new Runnable() {public void run() {h.process();}})
   t.start();
   threads.add(t);
  }
  for (Thread t : threads)
   t.join();
 }
}

public class PageHandler {
 public void process(int page) {
  Object o;
  prepareData();
  while((o = nextObject()) != null)
   stream.write(o);
 }
}

public class SiteHandler {
 public void process(int pagesAmount) {
  PageHandler handler = new PageHandler(stream);
  for (int i = 1; i <= pagesAmount; i++)
   handler.process(i);
 }

 public void process() {
  process(100);
 }
}

Баловство да и только

Здравствуйте, уважаемые.
Решил вести несколько блогов разных тематик. Мой первый блог о моей жизни в Java программировании мне нравится, но у него мало возможностей. На блогспот, думаю, я смогу раскрыться куда больше.