ВОПРОСЫ АБСОЛЮТНЫХ НОВИЧКОВ

[Tolik]

Yandex Maps for iPhone 4.1.0 хранит карты в одном файле Tiles.db

Кстати, новая версия МЯК для iPhone будет использовать тот же (новый) формат кэша, что и МЯК для других платформ, например, 3.91 бета для Symbian:
http://clubs.ya.ru/mobilemaps/replies.x ... maps-55758
Экспорта в этот новый формат пока нет, хотелка есть №658.

Бета-тестирование МЯК 4.2 для iPhone уже началось:
http://clubs.ya.ru/mobilemaps/replies.xml?item_no=55877

[kerby2000]

Тут есть что распараллеливать. Что думаете?

С такими исходными данными и с желанием "завоевать" весь мир (до последнего зума) надо смотреть в сторону распределённых вычислений. Просто распараллелить по ядрам толку будет немного.
Насколько хорошо именно параллелится экспорт в ябломяки - не могу сказать, не знаю алгоритма. Но из теории следует очевидная вешь, что не разнеся кэш по вычислительным нодам, принципиально не получится добиться ускорения больше единицы.

А вы бы не могли тут по подробней объяснить, почему распараллеливание по ядрам тут не поможет?
Вы считаете bottleneck'ом будет I/O, а не CPU ?
CUDA сообщает повышение обработки параллельных алгоритмов до 100 раз.
Вот я и хотел бы знать как алгоритм экспорта тут работает ?

[vasketsov]

А вы бы не могли тут по подробней объяснить, почему распараллеливание по ядрам тут не поможет?

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

Вы считаете bottleneck'ом будет I/O, а не CPU ?

Понятия не имею. Я не знаю алгоритма экспорта.

Общая логика такова. Пусть задача выполняется за время t на одном узле. На N узлах та же задача выполняется за время T. Тогда ускорение будет равно t/(TN). Понятно, что в обычных случаях при идеально распараллеливаемом алгоритме с отсутствием побочных затрат на синхронизацию и межузловое взаимодействие невозможно достичь ускорения больше 1. Чтобы решить задачу быстрее в N раз, обычно надо увеличить число узлов никак не меньше чем в N раз. Пример практически идеально распараллеливаемом задачи для SAS - это скачивание тайлов (для идеалистов - с нескольких сетевых интерфейсов, на несколько хардов,...), в простейшем случае один "поток" качает с одной стороны списка тайлов, другой - с другой. Условие остановки работы алгоритма известно заранее и не меняется (впрочем, алгоритм легко модифицируется и для случая докачивания области ответственности одного "потока" другим "потоком"), специальная синхронизация не нужна (как если бы потоки качали тайлы с одной стороны примерно по очереди через одного и не лезли вдвоём за одним тайлом). В общем, полная аналогия с каменщиками, кладущими стену из кирпичей. Но увеличить скорость более чем вдвое так не получится.

Здесь написано "обычно" - потому что бывают случаи, когда ускорение реально бывает больше 1. Чтобы понять, когда это бывает, надо в деталях знать алгоритм. Реальный пример могу привести, как задачи матфизики считают. Есть много процессоров, у каждого свой сетевой интерфейс и свой диск для данных - по сути процессорный кэш. Если общий массив даных не может быть поделён на все процессоры (а судя по всему это Ваш случай, ибо я не поверю, что в ближайшее будущее будет создан "железячный" кэш на сотню гигов и соответствующие бытовые процы с соответствующми коммуникациями) - придётся использовать "дорогую" скачку по сети во время работы (аналогия с бытовым компом весьма очевидна). Однако начиная с некоторого числа процессоров взаимодействие по сети скачкообразно сводится к минимуму (обусловленному обработкой граничиных условий, передачей данных между узлами и т.п.) - данные полностью попали в кэш. Впрочем, при дальнейшем увеличении количества вычислительных узлов ускорение где-то опять начнёт падать. Просто потому что невозможно любой параллельный аглоритм бесконечно масштабировать. Даже если (добиваясь максимальной производительности) строить стену в один кирпич толщиной и высотой (этакая дорожка из кирпичей), и каждый каменщик возьмёт по кирпичу и приготовится его поставить на место по команде, добавление новых каменщиков никак не скажется на скорости работы, а ускорение очевидно уменьшится (вследствие увеличения числа каменщиков). Поэтому определение оптимального числа вычислительных узлов является составной частью реализации параллельного алгоритма.

CUDA сообщает повышение обработки параллельных алгоритмов до 100 раз.

Ну, обещать-то можно многое. Например 2 - это тоже "до 100". Мой опыт в параллельным вычислениях говорит, что если серебряная пуля и существует, то явно не в этой области. Даже для казалось бы вдоль и поперёк изученных вычметодов решения уравнений матфизики не всегда известна (в смысле "доказана") оптимальная архитектура решения.

[zed]

гугл удалил снимки моего города. в Google Earth, по меню вид - исторические изображения, открыл карту города 2007 года. мне нужно ее выкачать для распечатки. как это можно следать с помощью SAS. планета?

Загляните сюда: viewtopic.php?f=9&t=1378

[zed]

Может быть, можно изменить алгоритм так, чтобы программа перебирала только тайлы из кэша и их экспортировала?

В общем-то, ничего невозможного нет. Только одно дело захотеть такой алгоритм, и совершенное другое - написать его.

SAS не хранит и не создаёт никаких индексов - т.е. программа банально не знает, что у неё и сколько лежит в кэше, поэтому приходится действовать перебором. И такой перебор неплохо справляется для точечного экспорта - когда мы знаем что у нас в этом месте есть кэш и мы экспортируем только этот регион. Но естественно, такой метод спотыкается, если неразумные юзвери мы вдруг попытаемся экспортировать всю землю...

Как я уже писал в предыдущем письме, я готов взяться за разработку конвертера для iPhone 4 и для Yandex Maps for iPhone 4.1.0. Вы бы не могли прислать свои наработки, чтобы с нуля этим не заниматься. Мне бы хотя бы кусок кода, который у вас отвечает за экспорт в iPhone ver 2.2+. Я попробую написать консольный конвертер под Линуксом, у меня кеш стоит на RAID5 c XFS и проблем со скоростью доступа к файлам не должно быть, ну а если и будут, можно все файлы в рамдиск перенести.

Если что, SAS написан на делфях и с линуксом как бы не очень (только через wine). Если вы готовы взяться за разработку, то должны понимать, что писать надо под windows и на паскале. А с вопросом "прислать свои наработки" вам следует обратиться к feya (в ЛС). Конечно, сомневаюсь что он будет вам что-то высылать, но доступ к репозиторию с исходниками может открыть (а может и не открыть).

[Tolik]

программа банально не знает, что у неё и сколько лежит в кэше, поэтому приходится действовать перебором.

Я и предлагаю действовать перебором, только перебирать не тайлы в выделенной области, а файлы в директориях.
Далее возникает вопрос: легко ли узнать, попадает ли некий файл из кэша в выделенную область? Если легко (в смысле, быстро), то всё Ок.
Если нет - можно сделать такую кривоватую фичу: экспортировать все файлы в кэше, без всякого выделения области.

Иногда это имеет-таки смысл, например, в описанном случае. Я и сам на днях скачал гугло-карту Китая в пустой кэш (конечно, весь Китай только до 9-го зума, а подробнее отдельные области). И такой экспорт всего кэша в одно касание мне бы очень помог (а то пришлось танцевать с бубном, как описано выше).

Заметьте, мой кэш получился всего 10 тыс. файлов (зумы с 1 по 17). А если экспортировать его имеющимся алгоритмом, выделив весь Китай и все зумы (с 1 по 17), надо перебрать порядка 100 миллионов! На 4 порядка больше.

[zed]

Я и предлагаю действовать перебором, только перебирать не тайлы в выделенной области, а файлы в директориях.

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

[Tolik]

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

Я об этом и спросил. Если так, то надо оставить текущий экспорт и добавить новый - без проверки выделения.

[Parasite]

добавить новый - без проверки выделения.

И как же Вы себе представляете тему "Программа понятия не имеет, сколько чего у нее в кэше - и узнает это лишь при полном переборе"? Индексатора-то в программе нет.
Без учета выделения программа будет перебирать вообще все доступные на зуме тайлы, чтобы узнать - есть ли хоть что-то из этого в пользовательском кэше (то есть, макс.число вариантов -> то есть, самый долгий экспорт из всех + нагрузка на диск на все эти миллиарды тайлов, из которых в кэше вообще может не быть ни одного. Проверить-то их придется все до последнего).

С другой стороны - можно подойти к вопросу через рекурсивный обход папок кэша, и вываливание в экспорт всего что найдется. Но что-то мне такая идея не нравится - по смыслу САСа она какая-то кривая, имхо...

[Tolik]

Нет, вы не поняли идею.
Например, надо экспортировать зум 17.
Открываем директорию map\z17, в ней лежит 1000 файлов (в моём примере).
Берём каждый и экспортируем.
Работаем всего с одной тысячей файлов, а не с четырьмя миллиардами.

P.S. ответил, когда не было последней фразы про рекурсивный обход папок. Да, именно это я и предлагаю. И да, я этот алгоритм уже назвал кривым. Зато весьма эффективным.