Я часто решаю какие-то конкретные, практические задачки. Постараюсь выкладывать здесь обзоры тех, которые показались мне наиболее интересными или необычными, чтобы работодателям был понятен уровень и опыт соискателя.
Время на разработку - чуть более суток.
Реализация на PHP + Bootstrap + JQuery.
База данных: файл .users и папка games с файлами всех игр.
Реализована на паттерне MVC и ООП.
Мультиязычный интерфейс (русский и английский).
Репозиторий на BitBucket: https://github.com/mega-t72/tic-tac-toe/
Ссылка на сайт c игрой (OpenShift): http://tictactoe-test72.rhcloud.com/
Ссылка на сайт c игрой (нестабильный хостинг от hostinger.ru): http://mega-tic-tac-toe.esy.es/
При анонимном входе на сайт производится перенаправление на страницу входа в учетную запись. Здесь можно либо зарегистрировать нового пользователя, либо войти в ранее созданную учетную запись. После ввода корректных данных авторизации, производится перенаправление на главную страницу.
Страница разделена на 3 части:
- верхняя панель инструментов,
- правая панель пользователей/игр,
- и основная часть - игровое поле.
На панели инструментов:
- кнопка выхода из текущей учетной записи
- перключатель маркера "крестик/нолик", которым будет играть пользователь в "своих играх"
- переключатель языка (поддержка русского и английского)
На панели пользователей/игр:
- список всех пользователей, в котором текущий пользователь выделен, а остальным можно послать приглашение в игру, если оно еще не было отправлено
- список "своих игр" - игр, которые инициирует текущий пользователь
- список "чужих игр" - игры, которые инициируют остальные пользователи
Заголовок игры содержит имя оппонента. Пользователь может выступать в роли инициатора игры или оппонента. Инициатор, отправив приглашение, дожидается одобрения со стороны оппонента и имеет право на первый ход. Оппонент либо соглашается на игру, либо отвергает приглашение. В случае, если приглашение отвергается, инициатор перенаправляется на главную страницу.
Игровое поле состоит из трех частей:
- само поле игры, состоящее из девяти кнопок
- строку статуса игры, в которой пишется чей текущий ход, кто проиграл/выиграл
- маркер игрока текущего хода
По окончании игры, инициатору предлагается повторить игру, в таком случае оппоненту автоматически приходит приглашение. Играть можно одновременно в несколько партий, с несколькими игроками. В списке чужих игр, неотвеченные приглашения подсвечиваются анимацией.
Delphi: сортировщик строк
1. Дан текстовый файл в ANSI кодировке размером от 100Кб до 10 Гб.
2. Элемент – это строка файла заканчивающаяся CRLF.
3. Размер строки может быть до 500 символов.
4. Необходимо отсортировать элементы по первым 50 символам.
5. Результат сортировки должен быть записан в новый файл.
2. По возможности максимально использовать 4х ядерный процессор
Репозиторий на GitHub: https://github.com/mega-t72/sorter-test
Время на разработку - трое суток. Честно говоря, у меня на нее ушло около недели. С виду, задачка, конечно простая, если бы не 1МБ. Быть может, уложился бы в 3 дня, если бы не майские праздники.
Т.к. требуется параллельное решение, а работа в основном ведется с HDD, то я решил максимально задействовать потоковые методы: просто разделить файл на 4 части и параллельно их сортировать быстро не получится - все равно скорость HDD будет определять скорость работы алгоритма. Поэтому я делаю следующие вещи:
1. Делю исходный буфер (1мб) на 4 части (по 256кб). Каждый буфер будет обрабатывать свой поток.
2. Итерационно считываю в каждый буфер порцию исходного файла
3. Анализирую и упаковываю каждый буфер: вычисляю длину каждой строки, обрезаю ее по границе 50 символов (если это требуется). Буфер наполняю так, чтобы в нижней его части собирались упакованные строки, а в верхней части - массив длин соответствующих строк. Помимо этого, я расчитываю наполнение буфера таким образом, чтобы в него вместилось еще 2 массива: массив указателей на строки - для быстрого индексированного доступа к каждой строке и массив индексов - для быстрой сортировки строк (все это можно уже делать параллельно, в потоках). Таким образом, структура буфера состоит из 4 частей:
Откуда взялись такие размерности массивов? Если брать случай с максимальным содержанием строк, то это будет случай, когда в буфере все строки имеют нулевую длину. В таком случае, на каждую строку требуется как минимум 2 байта (на хранение длины строки) и 4 байта - на хранение указателя, т.е. 256кб / 6байт - это 43690 строк (не более 2 байт на индекс). Таким образом, буфер может вместить максимум 256кб / 8байт - это 32768 строк без потери целостности массивов. Конечно, следует расчитать и случай, когда в буфере будет минимальное число строк - это когда все строки имеют длину более или равную 50 символам (по условию задачи). В таком случае буфер может вместить максимум 256кб / 58байт - это 4519 строки.
Но в обоих случаях мы будем в огромном выигрыше, по сравнению с беспотоковыми алгоритмами (если бы читали по одной строке на каждую итерацию), т.к. за одну дисковую операцию можем обработать сразу от 4519 до 32768 строк.
Помимо этого, скорость сортировки будет максимальной за счет:
Поскольку на 3 этапе производилась сортировка строк, то в файле эти строки уже упорядочены. Размер данных требуется для того, чтобы можно было быстро переместиться к следующему частичному результату сортировки, не разбирая структуру текущего. Число строк используется для расчета итераций по строкам (в принципе, на данном этапе оптимизации я даже могу отказаться от этого поля). Смещение строки требуется для быстрого доступа к строке (на финальной стадии сортировки). По длине строки определяется размер упакованной строки и размер конечной строки (на финальной стадии сортировки), которую требуется считать и записать в файл.
5. Все частичные результаты должны быть редуцированы в один конечный. Для этого я запускаю итерации Merge (слияние), в которых каждая пара результатов объединяется в один. Итерации проводятся до тех пор, пока не останется только одна результирующая последовательность структурированных строк. Здесь я так же применяю потоковую технологию чтения и записи данных, только со спецификой для алгоритма слияния. Поскольку здесь нам требуется уже 2 буфера строк, то я делю исходный буфер на 3 части:
В начале каждой итераций производится заполнение обоих буферов, с учетом остатка с предыдущей итерации (если он был). Далее, производится слияние правой последовательности в левую (с использованием выделенного ранее буфера обмена в 60 байт). В конце каждой итерации левая последовательность записывается в файл, в редуцирующую последовательность. Все итерации можно выполнять параллельно, в 4 потоках.
6. Полученная последовательность уже упорядочена, но ее необходимо преобразовать из структурированного вида обратно, в текстовый. Для этого я уже использую весь буфер с потоковым чтением в 1мб за минусом 502 байт, которые используются для хранения каждой строки при перемещении: последовательно считываю структурированные строки в буфер, после чего поочередно обрабатываю каждую строку в этом буфере. По смещению читаю данные из исходного файла в буфер (502 байта) и записываю в конечный файл.
---
Для хранения частичных результатов используется тот же файл, просто я записываю данные со смещением, равным размеру исходного файла, а после 6 этапа обрезаю файл на границе последней строки, таким образом сразу подчищая временные данные. Самая медленная стадия - это 6 этап, т.к. здесь каждой строке соответствует одна дисковая операция.
3. Размер строки может быть до 500 символов.
4. Необходимо отсортировать элементы по первым 50 символам.
5. Результат сортировки должен быть записан в новый файл.
Ограничения и требования:
1. Доступная для приложения память 1 Мб.2. По возможности максимально использовать 4х ядерный процессор
Репозиторий на GitHub: https://github.com/mega-t72/sorter-test
Время на разработку - трое суток. Честно говоря, у меня на нее ушло около недели. С виду, задачка, конечно простая, если бы не 1МБ. Быть может, уложился бы в 3 дня, если бы не майские праздники.
Т.к. требуется параллельное решение, а работа в основном ведется с HDD, то я решил максимально задействовать потоковые методы: просто разделить файл на 4 части и параллельно их сортировать быстро не получится - все равно скорость HDD будет определять скорость работы алгоритма. Поэтому я делаю следующие вещи:
1. Делю исходный буфер (1мб) на 4 части (по 256кб). Каждый буфер будет обрабатывать свой поток.
2. Итерационно считываю в каждый буфер порцию исходного файла
3. Анализирую и упаковываю каждый буфер: вычисляю длину каждой строки, обрезаю ее по границе 50 символов (если это требуется). Буфер наполняю так, чтобы в нижней его части собирались упакованные строки, а в верхней части - массив длин соответствующих строк. Помимо этого, я расчитываю наполнение буфера таким образом, чтобы в него вместилось еще 2 массива: массив указателей на строки - для быстрого индексированного доступа к каждой строке и массив индексов - для быстрой сортировки строк (все это можно уже делать параллельно, в потоках). Таким образом, структура буфера состоит из 4 частей:
-
1. упакованные строки (от 0 до 50 байт на строку)
2. массив индексов (по 2 байта на индекс)
3. массив указателей на строки (по 4 байта на указатель)
4. реверсивный массив длин строк (по 2 байта на длину)
Откуда взялись такие размерности массивов? Если брать случай с максимальным содержанием строк, то это будет случай, когда в буфере все строки имеют нулевую длину. В таком случае, на каждую строку требуется как минимум 2 байта (на хранение длины строки) и 4 байта - на хранение указателя, т.е. 256кб / 6байт - это 43690 строк (не более 2 байт на индекс). Таким образом, буфер может вместить максимум 256кб / 8байт - это 32768 строк без потери целостности массивов. Конечно, следует расчитать и случай, когда в буфере будет минимальное число строк - это когда все строки имеют длину более или равную 50 символам (по условию задачи). В таком случае буфер может вместить максимум 256кб / 58байт - это 4519 строки.
Но в обоих случаях мы будем в огромном выигрыше, по сравнению с беспотоковыми алгоритмами (если бы читали по одной строке на каждую итерацию), т.к. за одну дисковую операцию можем обработать сразу от 4519 до 32768 строк.
Помимо этого, скорость сортировки будет максимальной за счет:
-
1. Прямой доступ к строке (по массиву указателей)
2. Сортировка производится только по массиву индексов, а не строк (т.е. во время сортировки перемещаются только 2-байтовые индексы)
3. Метод сортировки: Хоара (quick sort)
-
1. Размер данных (8 байт)
2. Число строк
3. массив строк, состоящий из трех записей:
-
1. смещение строки в исходном файле (8 байт)
2. длина строки (2 байта)
3. первые символы строк (максимум 50)
Поскольку на 3 этапе производилась сортировка строк, то в файле эти строки уже упорядочены. Размер данных требуется для того, чтобы можно было быстро переместиться к следующему частичному результату сортировки, не разбирая структуру текущего. Число строк используется для расчета итераций по строкам (в принципе, на данном этапе оптимизации я даже могу отказаться от этого поля). Смещение строки требуется для быстрого доступа к строке (на финальной стадии сортировки). По длине строки определяется размер упакованной строки и размер конечной строки (на финальной стадии сортировки), которую требуется считать и записать в файл.
5. Все частичные результаты должны быть редуцированы в один конечный. Для этого я запускаю итерации Merge (слияние), в которых каждая пара результатов объединяется в один. Итерации проводятся до тех пор, пока не останется только одна результирующая последовательность структурированных строк. Здесь я так же применяю потоковую технологию чтения и записи данных, только со спецификой для алгоритма слияния. Поскольку здесь нам требуется уже 2 буфера строк, то я делю исходный буфер на 3 части:
-
1. для левой выборки строк ( (256кб - 60байт) / 2)
2. для правой выборки строк ( (256кб - 60байт) / 2)
3. для буфера обмена элементов между выборками. (60 байт)
В начале каждой итераций производится заполнение обоих буферов, с учетом остатка с предыдущей итерации (если он был). Далее, производится слияние правой последовательности в левую (с использованием выделенного ранее буфера обмена в 60 байт). В конце каждой итерации левая последовательность записывается в файл, в редуцирующую последовательность. Все итерации можно выполнять параллельно, в 4 потоках.
6. Полученная последовательность уже упорядочена, но ее необходимо преобразовать из структурированного вида обратно, в текстовый. Для этого я уже использую весь буфер с потоковым чтением в 1мб за минусом 502 байт, которые используются для хранения каждой строки при перемещении: последовательно считываю структурированные строки в буфер, после чего поочередно обрабатываю каждую строку в этом буфере. По смещению читаю данные из исходного файла в буфер (502 байта) и записываю в конечный файл.
---
Для хранения частичных результатов используется тот же файл, просто я записываю данные со смещением, равным размеру исходного файла, а после 6 этапа обрезаю файл на границе последней строки, таким образом сразу подчищая временные данные. Самая медленная стадия - это 6 этап, т.к. здесь каждой строке соответствует одна дисковая операция.
WEB: игра "Крестики-нолики"
Многопользовательская логическая игра.Время на разработку - чуть более суток.
Реализация на PHP + Bootstrap + JQuery.
База данных: файл .users и папка games с файлами всех игр.
Реализована на паттерне MVC и ООП.
Мультиязычный интерфейс (русский и английский).
Репозиторий на BitBucket: https://github.com/mega-t72/tic-tac-toe/
Ссылка на сайт c игрой (OpenShift): http://tictactoe-test72.rhcloud.com/
Ссылка на сайт c игрой (нестабильный хостинг от hostinger.ru): http://mega-tic-tac-toe.esy.es/
При анонимном входе на сайт производится перенаправление на страницу входа в учетную запись. Здесь можно либо зарегистрировать нового пользователя, либо войти в ранее созданную учетную запись. После ввода корректных данных авторизации, производится перенаправление на главную страницу.
Страница разделена на 3 части:
- верхняя панель инструментов,
- правая панель пользователей/игр,
- и основная часть - игровое поле.
На панели инструментов:
- кнопка выхода из текущей учетной записи
- перключатель маркера "крестик/нолик", которым будет играть пользователь в "своих играх"
- переключатель языка (поддержка русского и английского)
На панели пользователей/игр:
- список всех пользователей, в котором текущий пользователь выделен, а остальным можно послать приглашение в игру, если оно еще не было отправлено
- список "своих игр" - игр, которые инициирует текущий пользователь
- список "чужих игр" - игры, которые инициируют остальные пользователи
Заголовок игры содержит имя оппонента. Пользователь может выступать в роли инициатора игры или оппонента. Инициатор, отправив приглашение, дожидается одобрения со стороны оппонента и имеет право на первый ход. Оппонент либо соглашается на игру, либо отвергает приглашение. В случае, если приглашение отвергается, инициатор перенаправляется на главную страницу.
Игровое поле состоит из трех частей:
- само поле игры, состоящее из девяти кнопок
- строку статуса игры, в которой пишется чей текущий ход, кто проиграл/выиграл
- маркер игрока текущего хода
По окончании игры, инициатору предлагается повторить игру, в таком случае оппоненту автоматически приходит приглашение. Играть можно одновременно в несколько партий, с несколькими игроками. В списке чужих игр, неотвеченные приглашения подсвечиваются анимацией.
Комментариев нет:
Отправить комментарий