Список пространств имен в структуру каталогов

Список пространств имен в структуру каталогов

Мотивация

У меня есть список пространств имен, которые я извлек из типов, и я создаю структуру каталогов, представляющую эти пространства имен. Так что я могу разместить файл по пути пространства имен каждого типа. Самый простой способ — заменить . разделитель с \, и положить этому конец. Но я хочу быть фантазией, поэтому я поставил себе цель минимизировать количество создаваемых каталогов.

Метод

Я делаю это, не создавая каталог, когда не существует типа с пространством имен, вместо этого сохраняю . где это.

split all namespaces into their segments
for each unique namespace in namespaces
  for each segment in namespace, index i
    list all namespaces where segments are equal as shared
    if shared has lost namespaces compared to previous shared
      for each namespace[i] previous shared
        replace '.' with '\' 
      replace '.' with '\' in namespace[i]
    set previous shared to shared
  add namespace to namespaces
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;  

public class Program
{
    public static void Main()
    {
        string[] namespaces = new[] { // Set namespaces from types
            "Root.Sub11.Sub11.Sub3",
            "Root.Sub11.Sub11",
            "Root.Sub11.Sub21",
            "Root.Sub11.Sub21.Sub12",
            "Root.Sub11.Sub21.Sub13.Sub14",
            "Root.Sub11.Sub21.Sub13.Sub14",
            "Root.Sub11.Sub21.Sub13.Sub14",
            "Root.Sub11.Sub21.Sub13.Sub14.Sub47",
        };
        /* Should result in this list of directories:
         * Root.Sub11/Sub11/Sub3
         * Root.Sub11/Sub11
         * Root.Sub11/Sub21
         * Root.Sub11/Sub21/Sub12
         * Root.Sub11/Sub21/Sub13.Sub14
         * Root.Sub11/Sub21/Sub13.Sub14/Sub47
         */
        NamespacesToDirectoryStructure(namespaces.Select(n => n.Split(".")));
        var sb = new StringBuilder();
        foreach(var dir in typeNamespaceToPathMap.Values)
        {
            sb.AppendLine(new string(dir));
        }
        Console.WriteLine(sb.ToString());
    }
    
    private static readonly IDictionary<string[], char[]> typeNamespaceToPathMap = new Dictionary<string[], char[]>();

    private static void NamespacesToDirectoryStructure(IEnumerable<string[]> namespaces)
    {
        IList<string[]> processedTypeNamespaces = new List<string[]>();
        foreach (string[] segments in namespaces
                 .Distinct(new StringSequenceEqualityComparer())
                 .OrderBy(n => n.Length))
        {
            int segment = 0;
            char[] path = string.Join('.', segments).ToCharArray();
            IList<int> sharedNamespacePortionIndices;
            IList<string[]> sharedNamespacePortions = processedTypeNamespaces;
            do
            {
                // All namespaces, that share the segment and all previous with this.
                sharedNamespacePortionIndices = IndexOfAll(sharedNamespacePortions, segments, segment).ToList();
                if (segment != 0)
                {
                    // All namespaces, that share all previous segments with this.
                    IList<int> indices = sharedNamespacePortionIndices;
                    IEnumerable<string[]> removedNamespaces = TakeWhere(sharedNamespacePortions, (i, x) => !indices.Contains(i));
                    if (removedNamespaces.Any())
                    {
                        // Convert the [.] to [] to indicate a path branching for all that share previous segments
                        int charIndex = segments.Take(segment).Select(s => s.Length).Aggregate(0, (x, y) => x + y + 1) - 1;
                        path[charIndex] = '\';
                        foreach (char[] value in typeNamespaceToPathMap
                                 .Where(kvp => kvp.Value.Length > charIndex && (ReferenceEquals(kvp.Key, segments) || sharedNamespacePortions.Contains(kvp.Key)))
                                 .Select(kvp => kvp.Value))
                        {
                            value[charIndex] = '\';
                        }
                    }

                }
                sharedNamespacePortions = TakeWhere(sharedNamespacePortions, (i, x) => sharedNamespacePortionIndices.Contains(i)).ToList();
                segment++;
            } while (segment < segments.Length && sharedNamespacePortions.Count > 0);

            processedTypeNamespaces.Add(segments);
            typeNamespaceToPathMap.Add(segments, path);
        }
    }

    // Enumerates all items of the collection where the segment is equal to the segment at the same position - specified by segment - in test.
    private static IEnumerable<int> IndexOfAll(IList<string[]> collection, string[] test, int segment)
    {
        for (int index = 0; index < collection.Count; index++)
        {
            if (collection[index].Length > segment && String.Equals(test[segment], collection[index][segment], StringComparison.Ordinal))
            {
                yield return index;
            }
        }
    }

    private static IEnumerable<string[]> TakeWhere(IList<string[]> collection, Func<int, string[], bool> predicate)
    {
        for (int i = 0; i < collection.Count; i++)
        {
            if (predicate(i, collection[i]))
            {
                yield return collection[i];
            }
        }
    }

    private class StringSequenceEqualityComparer : IEqualityComparer<string[]>
    {
        public bool Equals(string[] x, string[] y)
        {
            if (x is null || x.Length != y?.Length)
                return false;
            for(int i = 0; i < x.Length; i++)
            {
                if (!x[i].Equals(y[i], StringComparison.Ordinal))
                    return false;
            }
            return true;
        }

        public int GetHashCode(string[] obj) => obj.GetHashCode(true);
    }
}

///<summary>Source: https://github.com/ProphetLamb-Organistion/Groundbeef/blob/master/src/Collections/Collections/CollectionHashing.cs</summary>
public static class CollectionHashing
{
    public static int GetHashCode(this IList list, bool fromValues)
    {
        if (list is null)
            throw new ArgumentNullException(nameof(list));
        if (!fromValues)
            return list.GetHashCode();
        int length = list.Count;
        if (length == 0)
            throw new ArgumentException(nameof(list), "List cannot be empty");
        int c = 0;
        for (int i = 0; i < length; i++)
        {
            object value = list[i] ?? throw new NullReferenceException("Value cannot be null");
            c = CombineHashCodes(c, value.GetHashCode());
        }
        return c;
    }
    
    internal static int CombineHashCodes(int h1, int h2)
    {
        return ((h1 << 5) + h1) ^ h2;
    }
}

Код на dotnetfiddle

Проблема

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

Вопрос

Поэтому мне нужны все мнения, которые я могу получить

  • A: как оптимизировать существующий код, или
  • B: о принципиально ином подходе к проблеме, который дает более простое решение.

Заранее спасибо и удачного кодирования!

Изменить: исправить Distinct-предложение: реализовать IEqualityComparer<>.GetHashCodeи потерять доверие к IEnumerable<>.SequenceEquals.

1 ответ
1

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

// A simple, specialised node class for your tree
class Node
{
    public bool Ends { get; private set; }
    public string Value { get; private set; }
    
    public List<Node> Children { get; private set; } = new List<Node>();

    private Node GetOrAddChild(string value)
    {
        var child = Children.FirstOrDefault(c => c.Value == value);
        if (child == null)
        {
            child = new Node { Value = value };
            Children.Add(child);
        }
        return child;
    }

    public void AddPath(string path) => AddPath(this, path);

    public static void AddPath(Node n, string path)
    {
        if (string.IsNullOrEmpty(path))
            return;
            
        var idx = path.IndexOf(".");
        if (idx == -1)
        {
            var child = n.GetOrAddChild(path);
            child.Ends = true;
        }
        else
        {
            var part = path.Substring(0, idx);
            var child = n.GetOrAddChild(part);
            AddPath(child, path.Substring(idx + 1));
        }
    }
}

Используя это, вы затем создаете свое дерево со своими данными:

void Main()
{
    // build the tree
    Node root = new Node();
    string[] namespaces = new[] {
            "Root.Sub11.Sub11.Sub3",
            "Root.Sub11.Sub11",
            "Root.Sub11.Sub21",
            "Root.Sub11.Sub21.Sub12",
            "Root.Sub11.Sub21.Sub13.Sub14",
            "Root.Sub11.Sub21.Sub13.Sub14",
            "Root.Sub11.Sub21.Sub13.Sub14",
            "Root.Sub11.Sub21.Sub13.Sub14.Sub47",
        };
    foreach (var ns in namespaces)
    {
        root.AddPath(ns);
    }

    // Use the tree:
    GetDirectories(root).ToList();
}

Теперь, когда у вас есть дерево уникальных путей, можно просто пройти по дереву:

IEnumerable<string> GetDirectories(Node n)
{
    if (n.Ends)
    {
        yield return n.Value;
    }
    var separator = n.Children.Count == 1 && !n.Ends ? "." : "/";
    foreach (var c in n.Children)
    foreach (var path in GetDirectories(c))
    {
        yield return n.Value == null
            ? path
            : $"{n.Value}{separator}{path}";
    }
}

Я не проверял производительность этого кода, но считаю, что легче следить за тем, что происходит. Из-за этого вы также можете дополнительно специализировать древовидную структуру, например, хранить дочерние элементы в IDictionary<string, Node> вместо использования списков, чтобы ускорить процесс, изменив FirstOrDefault к TryGetValue.

Я считаю этот двухэтапный подход полезным шаблоном, когда алгоритм становится слишком сложным. Обычно это признак того, что у меня нет подходящей структуры данных для работы, и введение ее может значительно упростить реализацию. Приятным побочным эффектом является то, что вы можете легко добавить другие средства форматирования для вывода команд XML, HTML, mkdir или всего, что вам нужно, без необходимости изменения основного алгоритма.

  • 1

    На основании вашего ответа я создал класс дерева. Большое спасибо! Я все еще хотел бы преобразовать GetDirectories в итерационный алгоритм, но это неважно.

    — Рене Караннанте

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *