Свифт огромный словарь массивов, очень медленно - PullRequest
Новая
       21

Свифт огромный словарь массивов, очень медленно

0 голосов
/ 04 октября 2018

Я работаю над проектом в Swift, используя dictionary.

Этот словарь имеет тип [String : [Posting]].У меня есть около 200 тысяч различных «терминов» (ключей) для вставки, и для каждого термина у меня есть от 500 до 1000 объектов для добавления в список.Я знаю, что это странная практика, но у меня нет выбора, и я должен разобраться со всеми этими элементами.

Проблема в том, что это очень очень медленно, так как словарь становится больше.Я попытался переключиться на NSMutableDictionary, не повезло.

Моя addTerm функция вызывается каждый раз, когда мне нужно вставить элемент: 

   func addTerm(_ term: String, withId id: Int, atPosition position: Int) {

        if self.map[term] == nil {
            self.map[term] = [Posting]()
        }

        if self.map[term]!.last?.documentId == id {
            self.map[term]!.last?.addPosition(position)
        }
        else {
            self.map[term]!.append(Posting(withId: id, atPosition: position, forTerm: term))
        }
    }

РЕДАКТИРОВАТЬ :Я понял, что это не словарь, который вызывает все это отставание, а его массивы.Массивы перераспределяют слишком много при добавлении новых элементов, и лучшее, что я мог, было заменить их на ContiguousArray.

Ответы [ 2 ]

0 голосов
/ 15 октября 2018

Это довольно распространенная ловушка производительности, которая также наблюдается в:

Проблема связана с тем фактом, что массив, который вы изменяете ввыражение self.map[term]!.append(...) является временной изменяемой копией базового массива в хранилище словаря.Это означает, что на массив никогда не ссылаются однозначно, и поэтому его буфер всегда перераспределяется.

Эта ситуация будет исправлена ​​в Swift 5 с неофициальным введением обобщенных средств доступа, но до тех пор одно решение (как упомянуто воба вышеупомянутых вопроса и ответов) должны использовать Dictionary subscript(_:default:), который из Swift 4.1 может изменять значение непосредственно в хранилище.

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

Например, это может выглядеть так: 

class X {

  private var map: [String: [Posting]] = [:]

  private func withPostings<R>(
    forTerm term: String, mutations: (inout [Posting]) throws -> R
  ) rethrows -> R {
    return try mutations(&map[term, default: []])
  }

  func addTerm(_ term: String, withId id: Int, atPosition position: Int) {

    withPostings(forTerm: term) { postings in
      if let posting = postings.last, posting.documentId == id {
        posting.addPosition(position)
      } else {
        postings.append(Posting(withId: id, atPosition: position, forTerm: term))
      }
    }

  }
  // ...
}
0 голосов
/ 04 октября 2018

Общий подход, когда ваш код слишком медленный, состоит в том, чтобы профилировать его в Инструментах, чтобы выяснить, какие строки на самом деле занимают больше всего времени и откуда идти.В другом месте могут быть узкие места и т. Д. Запуск вашего приложения непосредственно из XCode также создает отладочную сборку, которая жертвует производительностью ради возможности отладки.Сборка релиза может работать намного лучше.

Кроме того, если ваша программа занимает большой объем памяти, система может изо всех сил пытаться сделать эту память доступной для вашего приложения.На не-iOS платформах это приведет к выгрузке памяти на диск, что значительно повлияет на производительность вашего приложения, так как система не может предвидеть, к каким элементам словаря будет обращаться дальше.

ЕслиТребования к памяти не несут ответственности за замедление, вот несколько подходов, которые я бы попробовал:

  • Если вы можете оценить количество элементов, которые вы хотите вставить в словарь, вы можетеиспользуйте dictionary.reserveCapacity(numberOfItems).По мере роста словаря может потребоваться изменение его размера, что может потребовать перестройки хеш-таблицы, которую тип словаря использует внутри.Этот подход также работает для массивов.

  • Swift предоставляет методы для автоматической группировки элементов в словарь с использованием общего ключа: Dictionary(grouping: collection, by: { item in item.property }).Этот подход может быть вычислительно более эффективным, поскольку все может быть обработано в одном пакете.

  • Другой подход может заключаться в использовании других типов данных, таких как древовидная карта, которые не требуют частыхперераспределениях.Однако Swift не предоставляет такой тип в стандартной библиотеке.

...