Wing Commander IV: Цена свободы

Процесс перевода игры "Wing Commander IV: Цена свободы"- в разгаре. Желающие опробовать то, что получилось, могут добраться сразу до описания перевода и ссылок на его скачивание, щёлкнув по этой ссылке.

Желающим посоучаствовать в переводе - рекомендую: полезные для переводчика ссылки - словари, книги, статьи и прочие материалы. Пополнение копилки приветствуется!

См. также:
Самая свежая тестовая сборка и инструкции по её установке
Бета-тестеры, wэлкам!
31 дек 2016

Upd 1:
В связи с участившимися постами здесь "чисто для поржать" - вынужден объясниться.
6 янв 2014

Upd 2:
Приглашаю желающих поучаствовать в переводе. Отозвавшиеся будут увековечены в финальных титрах. (Никаких более материальных благ, к сожалению, обещать не могу. )
27 мая 2014

Upd 3:
Наконец удалось пробить барьер несовместимости моего перевода с версией игры от GOG!!! Желающим опробовать - wэлкам!
2 окт 2014

 

Оно же "двоичная куча"? А как в ней искать? Когда-то я таким баловался, но много-много лет назад и и всё напрочь забыл, включая название книги, в которой вычитал. Что-то там "для программистов" или "из жизни программистов"... Напомни, пожалуйста!

---------- Сообщение добавлено в 15:44 ---------- Предыдущее сообщение размещено в 15:34 ----------

Хм. Это хорошо, если заранее точно знать минимальное расстояние L между заменами; тогда индексный файл будет меньше файла данных в L/4 раз. На скорую руку глянул в language.tre - увы, самые мелкие из подозреваемых всего по 102 байта. :-(

Не уловил: заменить указатели/смещения их разностями? Неэффективно, макс. расстояние между заменами - мегабайты, уменьшать длину записи с 32 до 20 бит - много не выиграешь. :-(

 

Тогда хеш-таблица бы работала.

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

 

Рыжий Тигра, ты куда то не в ту сторону думаешь.
вот смотри:

Файл индексов имеет структуру:
0000 адрес какой то строки в файле строк
0004
0008
...
FFFF

для формулы нам надо делить на эту разницу и получить несколько периодов, если имеет быть изменение значений периодов.

Ну, например:
if adress>6000h and adress<8000h then adress=INT(adress/100h)*4 +смещение этого блока адресов в индексном файле.

Работает всё это со скоростью чтения файлов.

 

Bato-San, не, это мало что даёт по сравнению с перебором, да ещё и требует нехилой обвязки. :-(

Вполне хватит. На тысячу подмен - десяток сравнений вполне годится.
Проблема в том, что я никогда с двоичными деревьями дела не имел. А то, что имел с двоичной кучей, ограничивалось сортировкой массива. А вот как из сортированного массива построить дерево - понятия не имею. Можешь подсказать где почитать? Особенно интересна идея с сортировочным деревом. Кучу я изучал по Бентли "Жемчужины творчества программистов", 1990, там про поиск в куче не было. :-(

PS. Для ускорить поиск - могу выделить пару десятков килобайт под бит-карту: есть хоть одна замена в данном килобайте файла или нет. Это уже позволит на глаз при 99% чтений не отвлекаться на поиск замен.

 

Рыжий Тигра, очень хорошо описаны множества у Ахо, Хопкрофта и Ульмана - "Построение и анализ вычислительных алгоритмов", гл.4. Ну еще - третий том Кнута...

Но с двоичным все проще. Список-то упорядоченный (иначе повесимся проверять, сколько замен попадает в одну строку вывода). Значит, просто берем элемент посредине, затем - посредине половины, затем посредине четверти... и т.д. нашего списка.

 

Э, неудобно - делить на шестнадцатушки список длины не кратной 16. :-( Я думал - у тебя есть способ прохода по куче, там красивше - надо не упополамывать, а удваивать и иногда прибавлять единицу. :-)

 

Это в принципе одно и то же.
Просто первым элементом в этои "дереве" пишут индекс середины, 2 и 3-м - середин первой и второй половины, 4-7 - середин четвертушек и т.д. Т.к. расчет простой, то проще посчитать по ходу дела, чем заранее и тратить место...
Если бы нам не требовалось хранить замены упорядоченно, то можно было бы, конечно, соответствующим образом перетасовать сам список...

 

ненене. Наконец понял причину такой любви к математике. Долго смеялся.
Надо просто правильно строить структуры данных. Один раз отсортировать всё по частоте использования и выбросить вычислительный блок нафиг из программы.

 

Bato-San, я не понимаю, чего именно кто-то из нас не понимает. Есть стомегабайтный файл и сто блоков подмены. За 400 мегабайт индексного файла задача решается буквально одним плевком - на время решения плевать, это разовая работа. Но 400 мег нету, могу дать от силы мегу файла и полста кил ОЗУ. Чего именно я не понимаю?

 

Только сейчас понял: а замену нельзя произвести заранее по единственной причине - поедут смещения? Но почему в этом случае тупо не забить эти фрагменты спецсимволом, а их смещения не загнать в хэш? А если неиспользуемых символов много/фрагменты длинные - можно и индексы в исходный файл втюхать.

 

У меня какой-то алгоритмический затык. Целочисленный. Не могу себе представить "индекс середины" массива нечётной длины. :-(((((((((((((

 

А не наоборот?

 

Нет, там хуже - нужно тащить с собой оба варианта: заменённый и не. Каждый по полгига в общей сложности. Не говоря уже про оперативную замену всего файлА в процессе отладки (поиграл по-русски - надо тут же глянуть, как было по-аглицки), про чтобы не напортить тем, кто будет патчить в файлах что-то ещё (простейший случай - .tre-файл оригинальный и после пересборки) и т.д.

Именно чтобы сохранилась возможность играть на языке оригинала. Если бы не - можно было бы сразу в .tre-файлах заменить раз навсегда и не париться. :-(

А что нам даст хэш смещения 0x123400 длины 0x0B для запроса чтения 0x1000 байт со смещения 0x122700? А со смещения 0x12271F?

---------- Сообщение добавлено в 18:29 ---------- Предыдущее сообщение размещено в 18:27 ----------

Это смотря от нуля считать или от единицы. Если от нуля, то для массива длиной 16 середина - 8, а если от единицы, то для длины 15 середина 8. Но чтобы то и другое - никак. Видимо, дефект проца. :-((((((((

 

Воопче-то, как ни считай, чтобы элемент был средним, слева и справа от него должно быть одинаковое число элементов, что возможно только при нечетном числе элементов...

Но нам пофигу. Придумайте вопрос "не больше?" и "больше" и всегда используйте только его. Прикиньте примерно середину плюс-минус лапоть. Всегда округляйте при делении в одну сторону. Само сойдется. Проверьте на маленьких кошках.

 

что этого достаточно. в мегу файла можно засунуть 262144 адресов строк подмены в файле. Кода чуток больше станет, но он в один проход отрабатывается, а не гоняется в цикле. Что по твоему быстрее - каждый раз считать синус или брать его значение из уже рассчитанной таблицы ? Озу нужно только если ты собираешься менять данные вне буфера чтения основных данных игры.

 

Рыжий Тигра, там же получается поиск по 2 индексам, если я правильно понял - смещение и длина. А если:
1) отсортировать тройки "смещение-длина-строка" по смещению
1 - смещение1 длина1 строка
2 - смещение1 длина2 строка
3 - смещение1 длина3 строка
4 - смещение2 длина1 строка
5 - смещение2 длина2 строка

2) добавить индекс смещений со ссылками на полный список.
смещение1 - 1
смещение2 - 4

Тогда при поиске не нужно шерстить список целиком, а сначала найти смещение в индексе, а потом длину для этого смещения в полном списке.

 

В таком случае я не понимаю, каким именно 262144 из 44500000 возможных значений смещения в .tre-файле эти адреса собираются соответствовать.
Лет'юшоуми, ОК?

---------- Сообщение добавлено в 18:55 ---------- Предыдущее сообщение размещено в 18:54 ----------

Ну. 44500000 возможных значений смещения и 16383 возможных значения длины. И что это нам даёт?

 

Это без повторов ? Ты бы хоть объяснил толком, сколько всего строк в наличии. А то при неполных данных задачку предлагаешь решать. И почему не больше метра то ? Что то тут не то...

 

Рыжий Тигра, если искать по полному списку сразу, то придётся пройти все варианты - максимум 44500000*16383 = 729 млрд.

А если искать сначала по индексу, то ищется среди 44500000+16383 вариантов - сперва смещения, а потом длины только для этого уже найденного смещения.

 

Val07og, что я ему и предлагаю - разделить структуры и ещё их по частоте использования отсортировать заранее для скорости.