Большие статические массивы замедляют загрузку классов, нужен лучший / более быстрый метод поиска

Question

У меня есть класс с парой статических массивов:

int [] с 17 720 элементами
строка [] с 17 720 элементами

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

В частности, это поиск имен символов Unicode. Первый массив является индексом для второго массива.

static readonly int[] NAME_INDEX = {<br> 0x0000, 0x0001, 0x0005, 0x002C, 0x003B, ...

static readonly string[] NAMES = {<br> "Exclamation Mark", "Digit Three", "Semicolon", "Question Mark", ...

Следующий код показывает, как используются массивы (с учетом кода символа). [Примечание: этот код не является проблемой производительности]

int nameIndex = Array.BinarySearch<int>(NAME_INDEX, code);<br> if (nameIndex > 0) { return NAMES[nameIndex]; }

Полагаю, я смотрю другие варианты того, как структурировать данные таким образом, чтобы 1) класс быстро загружался и 2) я мог быстро получить «имя» для заданного кода символа.

Разве я не должен хранить все эти тысячи элементов в статических массивах?

Обновление
Спасибо за все предложения. Я опробовал подход с использованием словаря, и производительность добавления всех записей кажется очень низкой.

Вот код с данными Unicode для проверки массивов и словарей http://drop.io/fontspace/asset/fontspace-unicodesupport-zip

Обновление решения
Я протестировал свои оригинальные двойные массивы (которые работают быстрее обоих вариантов словаря) с фоновым потоком для инициализации, и это немного помогло производительности.

Однако настоящий сюрприз - насколько хорошо работают бинарные файлы в потоках ресурсов. Это самое быстрое решение, обсуждаемое в этой теме. Спасибо всем за ваши ответы!

Answer 1

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

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

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

Answer 2

First

A Dictionary<int, string> будет работать намного лучше, чем ваши дуэльные массивы. Если не учитывать как эти данные попадают в массивы / словарь (жестко запрограммированные или считанные из другого места, например, из файла ресурсов), это все еще лучший и более интуитивный механизм хранения

Второй

Как и предлагали другие, делайте загрузку в другой теме. Я бы использовал вспомогательную функцию, чтобы помочь вам справиться с этим. Вы можете использовать такой подход:

public class YourClass
{
    private static Dictionary<int, string> characterLookup;
    private static ManualResetEvent lookupCreated;

    static YourClass()
    {
        lookupCreated = new ManualResetEvent(false);

        ThreadPool.QueueUserWorkItem(LoadLookup);
    }

    static void LoadLookup(object garbage)
    {
        // add your pairs by calling characterLookup.Add(...)

        lookupCreated.Set();
    }

    public static string GetDescription(int code)
    {
        if (lookupCreated != null)
        {
            lookupCreated.WaitOne();
            lookupCreated.Close();
            lookupCreated = null;
        }

        string output;

        if(!characterLookup.TryGetValue(code, out output)) output = null;

        return output;
    }
}

В вашем коде вызовите GetDescription, чтобы перевести ваше целое число в соответствующую строку. Если пользовательский интерфейс не вызывает этого до тех пор, пока вы не увидите заметное уменьшение времени запуска. Однако для безопасности я включил ManualResetEvent, который приведет к блокировке любых вызовов на GetDescription до полной загрузки словаря.

Answer 3

«Разве я не должен хранить все эти тысячи элементов в статических массивах?»

Гораздо лучшим способом было бы сохранить ваши данные в виде двоичного потока в ресурсах сборки и затем загрузить их из ресурсов. Это потребует дополнительных затрат на программирование, но, следовательно, не требует инициализации объекта.

Основная идея будет (без реального кода):

// Load data (two streams):
indices = ResourceManager.GetStream ("indexData");
strings = ResourceManager.GetStream ("stringData");

// Retrieving an entry:
stringIndex = indices.GetIndexAtPosition (char);
string = strings.GetStringFromPosition (stringIndex);

Если вы хотите действительно хорошее решение (даже для какой-то еще работы), изучите использование файлов данных memmapped.

Answer 4

1. Инициализируйте ваши массивы в отдельном потоке, который не будет блокировать пользовательский интерфейс
2. http://msdn.microsoft.com/en-us/library/hz49h034.aspx

Answer 5

А как насчет использования словаря вместо двух массивов? Вы можете инициализировать словарь асинхронно, используя поток или пул потоков. Поиск будет также O (1) вместо O (log (n)).

public static class Lookup
{
  private static readonly ManualResetEvent m_Initialized = new ManualResetEvent(false);
  private static readonly Dictionary<int, string> m_Dictionary = new Dictionary<int, string>();

  public static Lookup()
  {
    // Start an asynchronous operation to intialize the dictionary.
    // You could use ThreadPool.QueueUserWorkItem instead of creating a new thread.
    Thread thread = new Thread(() => { Initialize(); });
    thread.Start();
  }

  public static string Lookup(int code)
  {
    m_Initialized.WaitOne();
    lock (m_Dictionary)
    {
      return m_Dictionary[code];
    }
  }

  private static void Initialize()
  {
    lock (m_Dictionary)
    {
      m_Dictionary.Add(0x0000, "Exclamation Point");
      // Keep adding items to the dictionary here.
    }
    m_Initialized.Set();
  }
}

Answer 6

если вы храните массивы в файле, вы можете выполнить ленивую загрузку

public class Class1
    {
        const int CountOfEntries = 17700; //or what ever the count is
        IEnumerable<KeyValuePair<int, string>> load()
        {
            using (var reader = File.OpenText("somefile"))
            {
                while (!reader.EndOfStream)
                {
                    var line = reader.ReadLine();
                    var pair = line.Split(',');
                    yield return new KeyValuePair<int, string>(int.Parse(pair[0]), pair[1]);
                }
            }
        }

        private static Dictionary<int, string> _lookup = new Dictionary<int, string>();
        private static IEnumerator<KeyValuePair<int, string>> _loader = null;
        private string LookUp(int index)
        {

            if (_lookup.Count < CountOfEntries && !_lookup.ContainsKey(index))
            {
                if(_loader == null)
                {
                    _loader = load().GetEnumerator();
                }
                while(_loader.MoveNext())
                {
                    var pair = _loader.Current;
                    _lookup.Add(pair.Key,pair.Value);
                    if (pair.Key == index)
                    {
                        return index;
                    }
                }
            }
            string name;
            if (_lookup.TryGetValue(index,out name))
            {
                return return name;
            }
            throw new KeyNotFoundException("The given index was not found");
        }
    }

код предполагает, что файл будет содержать одну пару в каждой строке, например: index0, NAME0 index1, name1

Если первый искомый индекс находится в конце, он, вероятно, будет работать медленнее (в основном из-за IO), но если доступ случайный, средний случай будет считывать половину значений в первый раз, если доступ не случайный, убедитесь, что сохранить наиболее часто используемые в верхней части файла

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

надеюсь, это поможет