Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Web программирование > SQL, базы данных
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.04.2014, 19:29   #1
Illusiony
Форумчанин
 
Регистрация: 17.02.2014
Сообщений: 881
По умолчанию Primary key >1,84467E+19

Необходимо создать таблицу MySQL для сбора статистической информации о матчах по игре «шашки».
В «шашках» имеется 32 используемых поля.
На каждом поле имеем 5 возможных комбинаций:
1)ничего не стоит
2)черная шашка
3) белая шашка
4)черная дамка
5)белая дамка
Если не учитывать многие невозможные комбинации то получаем 5^32=2,32831E+22.
Если возьмем четыре клетки то 5^4=625. Т.е 3 цифры с первой цифрой в 6 максимум для 4х клеток. 32/4=8. 8*3=24 знака числа необходимо для кодирования таким способом информации о состоянии игрового поля.
В MySQL самый большой тип целого числа это BIGINT с максимумом в 18446744073709551615 .Для моего случая это равносильно 18 знакам.( так как должно быть кратно3)
Первый вариант использование 2х полей: 1) BIGINT с 18 подходящими знаками+2) MEDIUMINT мне нужно 6 знаков от него. BIGINT= 8 бит, MEDIUMINT 3 байта в итого 11 байт и несколько неиспользуемых знаков.
Если взять строковый тип данных 1 байт =256(255) символов
Можно 5^3=125. То есть 1 символом можно прокодировать 3 клетки. 32/3≈11 символов и 11 байт данных.
Какой вариант первичного ключа лучше для скорости работы с таблицей?:
1) BIGINT +MEDIUMINT
2) CHAR(M)
Так вот собственно вопросы в каком виде хранить информацию о игровом поле учитывая некий компромисс между размером в байтах и сложностью кодирования –декодирования(и производительностью при работе с получившейся базой данных)?
В качестве первичного ключа к таблице будет как раз некий код.
Собственно структура таблицы :
Первичный ключ, далее некоторое количество полей с подобными кодами как в первичном ключе либо иным кодом соответствующим измененившимуся полю за 1 ход от того что был в качестве первичного ключа.
Сколько может максимально измениться количество клеток за 1 ход в «шашках»?
Illusiony вне форума Ответить с цитированием
Старый 08.04.2014, 19:35   #2
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

А зачем в ключ это все засовывать? Других полей не хватает для хранения информации в удобном виде? Чушь какая-то. А чтобы оценить эффективность создай разные варианты хранения и нещадно погоняй. Хотя и этого скорее всего будет мало для оценки
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 08.04.2014 в 19:37.
Аватар вне форума Ответить с цитированием
Старый 08.04.2014, 20:16   #3
Illusiony
Форумчанин
 
Регистрация: 17.02.2014
Сообщений: 881
По умолчанию

А потому что теоретически первичных ключей может быть близко к этому числу. И мне необходимо ассоциировать первичный ключ с вариантом расположения поля.
Ну да в принципе первичный ключ можно просто нумеровать 1,2 .... второе поле точно должно включать приведенный мною код либо похожий код. А так, как я буду искать информацию в таблице по этому полю где код, то зачем мне первичный ключ в виде 1,2 ....?
Illusiony вне форума Ответить с цитированием
Старый 08.04.2014, 20:35   #4
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

Как вариант, можно такой способ кодирования предложить. Большинство клеток пустые, пустые клетки можно кодировать 1 битом, записывая просто 0. Если бит 1, то следующий бит показывает цвет фигуры (0 - черная, 1 - белая), далее тип фигуры (0 - шашка, 1 - дамка). И того на пустые клетки по 1 биту, на заполненные по 3 бита. В худшем случае (начало игры) на 32 игровых клетках расположено 24 фигуры. То есть в худшем случае под всю доску потребуется 24*3+8=80 бит или 10 байт.

Идея хранить все возможные комбинации абсурдна, никакой памяти не хватит.
Arigato вне форума Ответить с цитированием
Старый 08.04.2014, 20:46   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Ладно, предположим есть сборный, допустим BIGINT ключ. Как по нем выборку делать? Только по маске - в результате ни какой индекс при выборке задействован не будет. Если он символьный, то там типа LIKE или SUBSTR и опять проблемы с индексами. Т.е. такой подход - максимально ухудшить эффективность запросов, даже простых
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 08.04.2014, 21:31   #6
Illusiony
Форумчанин
 
Регистрация: 17.02.2014
Сообщений: 881
По умолчанию

Цитата:
Сообщение от Arigato Посмотреть сообщение
Как вариант, можно такой способ кодирования предложить. Большинство клеток пустые, пустые клетки можно кодировать 1 битом, записывая просто 0. Если бит 1, то следующий бит показывает цвет фигуры (0 - черная, 1 - белая), далее тип фигуры (0 - шашка, 1 - дамка). И того на пустые клетки по 1 биту, на заполненные по 3 бита. В худшем случае (начало игры) на 32 игровых клетках расположено 24 фигуры. То есть в худшем случае под всю доску потребуется 24*3+8=80 бит или 10 байт.

Идея хранить все возможные комбинации абсурдна, никакой памяти не хватит.
Я и не отрицаю что хранение всех возможных комбинаций неосуществима, но некоторое весьма немаленькое количество возможных комбинаций все таки будет.
По вашему описанию , если учитывать позицию клетки в коде, то вы не учитываете что все таки каждая из 32 клетак в каком то ходу может быть в любом из 5 комбинаций. Я понимаю что в моем примере весьма большая избыточность, но как не использую весьма большие алгоритмы кодирования достичь урезание размера?

Да, фактически получается максимум 80 бит информации (1,20893E+24). Фактически число комбинаций меньше 5^32=2,32831E+22, но вопрос в том как закодировать-раскодировать данные. Если я теряю 1 байт, но получу алгоритм кодирования , который весьма сильно загружает процессор, то это для меня не выгодно. Как я и писал мне нужен некий компромисс размера-производительности, и желательно простоты.

Последний раз редактировалось Illusiony; 08.04.2014 в 21:37.
Illusiony вне форума Ответить с цитированием
Старый 08.04.2014, 21:32   #7
Illusiony
Форумчанин
 
Регистрация: 17.02.2014
Сообщений: 881
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Ладно, предположим есть сборный, допустим BIGINT ключ. Как по нем выборку делать? Только по маске - в результате ни какой индекс при выборке задействован не будет. Если он символьный, то там типа LIKE или SUBSTR и опять проблемы с индексами. Т.е. такой подход - максимально ухудшить эффективность запросов, даже простых
Извините я почти профан в этих вопросах. Я лишь предложил пару первых мыслей по этому поводу. Могли бы Вы предложить пару вариантов решения задачи?
Illusiony вне форума Ответить с цитированием
Старый 08.04.2014, 22:08   #8
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

Цитата:
Сообщение от Illusiony Посмотреть сообщение
По вашему описанию , если учитывать позицию клетки в коде, то вы не учитываете что все таки каждая из 32 клетак в каком то ходу может быть в любом из 5 комбинаций.
Значит вы не поняли ту схему, что я предложил. Под хранение любой возможной комбинации надо не более 10 байт. То есть в общем случае можно все это дело запихнуть в какой-нибудь 10-байтовый тип, типа Extended в Делфи (надо смотреть есть ли что-то подобное в конкретной реализации SQL).

На счет эффективности, то если значение рассматривать как просто 10 байт, а не вещественное число, то восстановление состояния доски или его запись сводится к последовательности поразрядных операций, число которых не превышает 80.

Последний раз редактировалось Arigato; 08.04.2014 в 22:12.
Arigato вне форума Ответить с цитированием
Старый 08.04.2014, 22:25   #9
eval
Подтвердите свой е-майл
 
Регистрация: 29.08.2012
Сообщений: 4,022
По умолчанию

я вот тоже не понял откуда такие космические цифры у автора?
в шахматах капейки сущие, .. давно как то на перле видел реализацию шахмат (одним глазом), там все просто и толково, а кода так ваще не более 100 строк (если не забыл), а тут шашки и такое неимоверное огого

автор поищите что уже готовое, хотя бы сильно приближенное, проанализируйте и поймете что да как..
eval вне форума Ответить с цитированием
Старый 08.04.2014, 22:44   #10
Illusiony
Форумчанин
 
Регистрация: 17.02.2014
Сообщений: 881
По умолчанию

Цитата:
Сообщение от eval Посмотреть сообщение
я вот тоже не понял откуда такие космические цифры у автора?
в шахматах капейки сущие, .. давно как то на перле видел реализацию шахмат (одним глазом), там все просто и толково, а кода так ваще не более 100 строк (если не забыл), а тут шашки и такое неимоверное огого

автор поищите что уже готовое, хотя бы сильно приближенное, проанализируйте и поймете что да как..
А Вы про что вообще? О чем речь какие 100 строк? Реч даже не о количестве строк кода, а сколько процессор будет этот код обрабатывать( кодировать-декодировать).
Ну предложите свой вариант? Много комбинаций? ок сколько же по вашему хватит и какие алгоритмы кодирования-раскодирования?

В шахматах вообще цифры невообразимые.
Illusiony вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Исправление ошибки Duplicate entry '21057' for key 'PRIMARY' provalenki Фриланс 1 23.10.2013 12:34
Как задать primary index Даниил_глазко БД в Delphi 6 08.01.2012 13:17
Не могу разобратся с primary key Progsenya SQL, базы данных 3 19.02.2011 10:27
Violation of primary key constraint .Cannot insert duplicate key in object Как избавиться? SlimFIT БД в Delphi 4 28.12.2010 06:46