Информация об изменениях

Сообщение Thread-safe словарь с авто-инкрементируемым значением от 31.01.2015 4:31

Изменено 31.01.2015 4:32 AJ

Старый текст
Новый текст
Разница

Дисклеймер: всегда писал на Java и только недавно стал пользоваться C#, так что просьба не обращать внимание на стиль

Для решения одной задачи понадобилось написать такой словарь, который бы было можно использовать из разных потоков и который бы реализовывал вот такой интерфейс

    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }

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

Если строка запрашивается впервые, то возвращаемый результат равен количеству строк на данный момент находящихся в словаре и автоматически инкрементируется. Нумерация начинается с нуля. "Дырки" в счетчике не допускаются, то есть если в словаре N строк, то набор индексов должен быть таким: 0, 1, 2, ..., N-1

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

Написал вот такой код, просьба подсказать, если есть более оптимальный вариант:

Решение

using System.IO;
using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Threading;

namespace A
{
    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }
    
    public class Indexer : IIndexer
    {
        private readonly ConcurrentDictionary<string, Record> _map =
            new ConcurrentDictionary<string, Record>();
            
        private int _counter = -1;
        
        public int GetIndex(string key)
        {
            return _map.GetOrAdd(key, k => new Record(this)).Index;
        }
        
        public int MaxIndex { get { return _counter; } }
        
        public static void Main()
        {
            var indexer = new Indexer();
            char[] alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
            Action action = () => 
            {
                foreach (var c in alpha)
                {
                    Console.WriteLine(indexer.GetIndex(c.ToString()));
                    Thread.Yield();
                }
            };
            
            var t1 = new Thread(() => action());
            var t2 = new Thread(() => action());
            var t3 = new Thread(() => action());
            var t4 = new Thread(() => action());
            
            t1.Start();
            t2.Start();
            t3.Start();
            t4.Start();
            
            t1.Join();
            t2.Join();
            t3.Join();
            t4.Join();
            
            var keys = new List<string>(indexer.Keys);
            keys.Sort();
            Console.WriteLine(indexer.MaxIndex + " " + String.Join(",", keys));
        }
        
        public IEnumerable<string> Keys
        {
            get
            {
                return _map.Keys;
            }
        }
        
        private class Record
        {
            private readonly Indexer _indexer;
            private int _index = -1;
            
            public Record(Indexer indexer)
            {
                _indexer = indexer;
            }
            
            public int Index
            {
                get
                {
                    if (_index >= 0)
                    {
                        return _index;
                    }
                    
                    lock (this)
                    {
                        if (_index < 0)
                        {
                            _index = Interlocked.Increment(ref _indexer._counter);
                        }
                        return _index;
                    }
                }
                
                private set
                {
                    _index = value;
                }
            }
        }
    }
}

Thread-safe словарь с авто-инкрементируемым значением

    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }

Решение

using System.IO;
using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Threading;

namespace A
{
    public interface IIndexer
    {
        IEnumerable<string> Keys { get; }
        int GetIndex(string key);
        int MaxIndex { get; }
    }
    
    public class Indexer : IIndexer
    {
        private readonly ConcurrentDictionary<string, Record> _map =
            new ConcurrentDictionary<string, Record>();
            
        private int _counter = -1;
        
        public int GetIndex(string key)
        {
            return _map.GetOrAdd(key, k => new Record(this)).Index;
        }
        
        public int MaxIndex { get { return _counter; } }
        
        public static void Main()
        {
            var indexer = new Indexer();
            char[] alpha = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray();
            Action action = () => 
            {
                foreach (var c in alpha)
                {
                    Console.WriteLine(indexer.GetIndex(c.ToString()));
                    Thread.Yield();
                }
            };
            
            var t1 = new Thread(() => action());
            var t2 = new Thread(() => action());
            var t3 = new Thread(() => action());
            var t4 = new Thread(() => action());
            
            t1.Start();
            t2.Start();
            t3.Start();
            t4.Start();
            
            t1.Join();
            t2.Join();
            t3.Join();
            t4.Join();
            
            var keys = new List<string>(indexer.Keys);
            keys.Sort();
            Console.WriteLine(indexer.MaxIndex + " " + String.Join(",", keys));
        }
        
        public IEnumerable<string> Keys
        {
            get
            {
                return _map.Keys;
            }
        }
        
        private class Record
        {
            private readonly Indexer _indexer;
            private int _index = -1;
            
            public Record(Indexer indexer)
            {
                _indexer = indexer;
            }
            
            public int Index
            {
                get
                {
                    if (_index >= 0)
                    {
                        return _index;
                    }
                    
                    lock (this)
                    {
                        if (_index < 0)
                        {
                            _index = Interlocked.Increment(ref _indexer._counter);
                        }
                        return _index;
                    }
                }
            }
        }
    }
}