Форум программистов, компьютерный форум, киберфорум
Наши страницы
Objective-C
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
kievkao
42 / 42 / 2
Регистрация: 22.11.2012
Сообщений: 225
#1

C/C++ vs Objective-C для обхода больших деревьев - вопрос оптимизации

16.01.2014, 19:46. Просмотров 1940. Ответов 20
Метки нет (Все метки)

Добрый день!

Появилась необходимость обрабатывать многотысячный словарь ("словарь" - буквально, набор слов): поиск вариантов различных комбинаций, и т.д.
Есть ли смысл реализовывать алгоритмическую часть на С/С++ для увеличения производительности (она критична), или особой разницы с использованием родного Objective-C не будет?

Раньше я писал на C/C++, так что с этими языками знаком.

Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2014, 19:46
Ответы с готовыми решениями:

Напишите программу обхода двоичных деревьев во внутреннем порядке
Помогите найти ошибку в коде. Задание: Напишите программу обхода двоичных...

HttpWebResponse для получения размеров нескольких файлов - вопрос оптимизации
Всем доброго времени суток! У меня есть много файлов, и я хочу узнать их...

Вопрос обхода решения в лоб.
Имеется форма на которой около 100 вычисляемых полей. Каждое поле имеет свой...

Задача об оптимизации хранении больших объемов строк
Приветствую. Вопрос на тему "а как лучше?". Храню строки, далее данные. Есть...

Вопрос по оптимизации
Делаю игру...Там есть очень много вычислений синусов , косинусов (в таймере в...

20
Megabar
22 / 22 / 7
Регистрация: 01.12.2013
Сообщений: 93
16.01.2014, 21:10 #2
kievkao, разницы никакой, компилятор один. Но будет зависеть от того, какую библиотечную функцию (STL или Apple SDK) будите использовать.
0
zulkis
684 / 611 / 43
Регистрация: 13.01.2011
Сообщений: 1,724
16.01.2014, 21:34 #3
Тут интересное чтиво про "массивы" в Cocoa.
Но это немного оффтоп.

По теме:
Я бы попробовал для начала то, что есть в стандарте. Но есть одно но
Я бы использовал CF нежели что-либо из NS (в данном случае CFDictionary).
Тут я думаю все очевидно, нет отправки лишних сообщений, исходник тут, бла бла.
И мне было бы Очень интересно посмотреть на ваши результаты. Если они будут, покажете?

Не по теме:

будите

:/

Update 1:
многотысячный словарь
Это сколько? 2 тысячи или 1000 тысяч?
Если 2 - не парьтесь
А если тысяча и выше...
2
mobidevelop
182 / 182 / 3
Регистрация: 10.01.2013
Сообщений: 596
17.01.2014, 01:46 #4
Цитата Сообщение от kievkao Посмотреть сообщение
Есть ли смысл реализовывать алгоритмическую часть на С/С++ для увеличения производительности (она критична), или особой разницы с использованием родного Objective-C не будет?
Будет. Механизм сообщений Obj-C чуть медленнее прямого вызова С/С++. Но это смотря что и как писать. Задача описана недостаточно подробно, чтобы что-то определенное посоветовать можно было.

Добавлено через 2 часа 48 минут
zulkis, не ссылка - клад!
0
glvrzzz
95 / 71 / 12
Регистрация: 12.12.2012
Сообщений: 214
17.01.2014, 06:29 #5
Цитата Сообщение от mobidevelop Посмотреть сообщение
Механизм сообщений Obj-C чуть медленнее прямого вызова С/С++.
Вроде не все так просто. Не могу найти ссылку, но насколько я помню, от самого быстрого к самому медленному:
1. вызов с-функции
2. вызов невиртуального c++ метода
3. вызов закешированного obj-c метода
4. вызов виртуального c++ метода
5. вызов незакешированного obj-c метода

kievkao, тут сложно вам сказать, не зная даже примерно, что за алгоритмы вы собираетесь реализовать, с каким количеством данных и какое быстродействие для вас будет приемлимым. Мне только вот кажется вы слишком заранее беспокоитесь о производительности. Как правило, наибольший выигрыш приносит не выбор языка, а оптимизация непосредственно алгоритмов. Я бы не задумываясь накидал реализацию на obj-c, а потом если что-то не устроит - измеряем, профилируем, ищем ботлнеки, переписываем критические куски, к примеру, на С.
1
kievkao
42 / 42 / 2
Регистрация: 22.11.2012
Сообщений: 225
17.01.2014, 14:45  [ТС] #6
Спасибо всем за отзывы!
Действительно, ссылка очень интересная, сейчас буду читать..

По поводу размера словаря - около 100000 слов.

Детальнее: есть в GooglePlay очень классная игра в стиле "Балды", (в очень приближенном стиле и значительно более простая в плане реализации, навскидку), аналога которой я не нашел в AppStore. Очень хотелось бы ее сделать, чтобы иметь свое второе, единолично реализованное, приложение. Для опыта, так сказать. Да и игра очень нравится, с удовольствием бы пользовался своей программой.

Для этой реализации особых ухищрений не надо - алгоритмическая часть будет заключаться, фактически, только в поиске наличия слова в словаре.
Но в плане словарных игр у меня есть еще пару идей, которые уже юзают словарь по полной - поиск всех вариантов слов из x конкретных букв, из x конкретных + y произвольных, и т.д.
Так что, изначально хотел узнать, как лучше организовать работу.
0
mobidevelop
182 / 182 / 3
Регистрация: 10.01.2013
Сообщений: 596
17.01.2014, 14:57 #7
Тогда все просто. NSArray of NSString и предикаты. Если быстродействие не устроит - думать дальше
1
zulkis
684 / 611 / 43
Регистрация: 13.01.2011
Сообщений: 1,724
17.01.2014, 18:39 #8
kievkao, а вы разбейте ваш словарь на 33 +-10 словарей
Или еще какой-нибудь метод придумайте(Их должно быть великое множество для работы со словами и поиском по ним). Масштабируйте задачу.
1
kievkao
42 / 42 / 2
Регистрация: 22.11.2012
Сообщений: 225
17.01.2014, 22:15  [ТС] #9
Цитата Сообщение от zulkis Посмотреть сообщение
kievkao, а вы разбейте ваш словарь на 33 +-10 словарей
Или еще какой-нибудь метод придумайте(Их должно быть великое множество для работы со словами и поиском по ним). Масштабируйте задачу.
Да, мысль - разбить словарь, ориентируясь по начальным буквам, интересная))

Кстати, написал по-быстрому метод простого поиска "в лоб" наличия слова в словаре - работает моментально, даже ничего разбивать не надо))
Перевел NSString в UTF-8 и погнал дальше через strcmp().

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

Добавлено через 1 час 24 минуты
Возможно, я немного не по теме, но вопрос очень актуален:

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

Как действовать в случае, если мне необходимо хранить такой изменяемый словарь?
Буду очень благодарен.
0
zulkis
684 / 611 / 43
Регистрация: 13.01.2011
Сообщений: 1,724
17.01.2014, 22:34 #10
В базу, либо через хэндл файла, если файл большой. В память то его может не получится весь сунуть разом.
Но лучше в базу.
1
mobidevelop
182 / 182 / 3
Регистрация: 10.01.2013
Сообщений: 596
17.01.2014, 22:48 #11
Просто не надо писать его в папку с ресурсами. Она read only. Нужно создать папку в папке приложения. Documents не советую - она шарится через iTunes.
0
noname_club
105 / 96 / 12
Регистрация: 01.05.2013
Сообщений: 603
21.01.2014, 12:15 #12
Появилась необходимость обрабатывать многотысячный словарь ("словарь" - буквально, набор слов): поиск вариантов различных комбинаций, и т.д.
можно под слова базу выделить (SQLite), в которой уже будет поиск этих слов индексирован

а все остальное, в силу его(словаря) простоты хранить в словаре
1
kievkao
42 / 42 / 2
Регистрация: 22.11.2012
Сообщений: 225
21.01.2014, 12:17  [ТС] #13
Цитата Сообщение от noname_club Посмотреть сообщение
можно под слова базу выделить (SQLite), в которой уже будет поиск этих слов индексирован

а все остальное, в силу его(словаря) простоты хранить в словаре
Спасибо.

Я правильно вам понимаю, вы имеете в виду именно взаимодействие напрямую с SQLite, без использования CoreData?
0
noname_club
105 / 96 / 12
Регистрация: 01.05.2013
Сообщений: 603
21.01.2014, 12:24 #14
да, напрямую
0
mobidevelop
182 / 182 / 3
Регистрация: 10.01.2013
Сообщений: 596
21.01.2014, 12:51 #15
kievkao, осторожнее с советами глубокоуважаемого noname_club. Они не всегда... как бы это... разумны. В частности, этот. Мало того, что в Core Data собрано (и отлажено!) множество оптимизирующих механизмов, так тут еще и сильно спорное утверждение по поводу индексации. Не умеет SQL индексировать строки иначе, чем по началу. А для вашей задачи это не особенно подходит. Точнее, недостаточно будет. Хотя, сама идея использования SQL-хранилища, правильная. Конечно, если массив в память не поместится. Потому как в памяти быстрее с данными оперировать.
0
zulkis
684 / 611 / 43
Регистрация: 13.01.2011
Сообщений: 1,724
21.01.2014, 14:19 #16
mobidevelop, +1, да и еще к тому же CoreData, это как бы так сказать... Не SQL

Не по теме:

- Вы эксперт в SQL?
- Нет.
- Так и напишем, эксперт в noSQL...

0
noname_club
105 / 96 / 12
Регистрация: 01.05.2013
Сообщений: 603
21.01.2014, 14:30 #17
Не умеет SQLite индексировать строки иначе, чем по началу
это типа тоже самое что сказать , что SQlite ваще не база данных
0
gazlan
3139 / 1915 / 311
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
21.01.2014, 15:31 #18
Мало того, что текст там хранится в UTF-8, так еще время уйдет на парсинг и выполнение SQL-запроса.

"многотысячный" - это "ни о чем". Если речь идет о словаре естественного языка (~100,000 базовых лексем в среднем по 10 символов), то это 1 Mb нетто. 3,000,000+ словарь всех русских слов - это примерно 100 Mb при компактном хранении - цифры вполне посильные.

TS невнятно изложил свои цели, но в любом случае, ему нужно либо Trie либо Key-Value DB (NoSQL).
1
noname_club
105 / 96 / 12
Регистрация: 01.05.2013
Сообщений: 603
21.01.2014, 15:33 #19
Не умеет SQLite индексировать строки иначе, чем по началу
как бы любая база может индексировать только по-началу. Это называется индексированный поиск. Автору темы он вроде и нужен.
0
mobidevelop
182 / 182 / 3
Регистрация: 10.01.2013
Сообщений: 596
21.01.2014, 15:55 #20
gazlan, дерево классное, но в этом случае его применить сложно будет. Тут же не только по началу искать придется. Новая буква в любом месте оказаться может. Хотя, если постараться... Блин! Хоть самому садиться писать!!!
0
21.01.2014, 15:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2014, 15:55

Вопрос оптимизации программы
Программу сообрал, но как показывает практика, она после некоторой стабильной...

Получение БД частями - вопрос оптимизации
Нужно разбирать БД по кускам, но проблема в том, что SELECT * FROM db_name...

Теоретический вопрос по оптимизации программы
В ходе работы моей программы создаются динамические компоненты на отдельной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru