반응형
HashSet에서 실제 항목을 검색하는 방법?
왜 불가능한 지에 대한 이 질문을 읽었 지만 문제에 대한 해결책을 찾지 못했습니다.
.NET에서 항목을 검색하고 싶습니다 HashSet<T>. 이 서명이있는 방법을 찾고 있습니다.
/// <summary>
/// Determines if this set contains an item equal to <paramref name="item"/>,
/// according to the comparison mechanism that was used when the set was created.
/// The set is not changed. If the set does contain an item equal to
/// <paramref name="item"/>, then the item from the set is returned.
/// </summary>
bool TryGetItem<T>(T item, out T foundItem);
이러한 방법으로 항목 집합을 검색하면 O (1)이됩니다. a에서 항목을 검색하는 유일한 방법 HashSet<T>은 O (n) 인 모든 항목을 열거하는 것입니다.
본인은이 문제 다음 내 자신을 만들기 위해 어떤 해결 방법을 찾을 수있다 HashSet<T>또는를 사용합니다 Dictionary<K, V>. 다른 생각은 없나요?
참고 : 에 항목
이 HashSet<T>포함되어 있는지 확인하고 싶지 않습니다 . 항목 HashSet<T>을 업데이트해야하므로에 저장된 항목에 대한 참조를 얻고 싶습니다 (다른 인스턴스로 대체하지 않음). 내가 전달할 항목은 TryGetItem동일하지만 (생성자에게 전달한 비교 메커니즘에 따라) 동일한 참조가 아닙니다.
요청하신 내용은 1 년 전에 .NET Core 에 추가 되었으며 최근 .NET 4.7.2에 추가되었습니다 .
.NET Framework 4.7.2에서는 다음과 같이 새로운 기능을 활성화하는 몇 가지 API를 표준 컬렉션 유형에 추가했습니다.
- 'TryGetValue'가 SortedSet 및 HashSet에 추가되어 다른 컬렉션 유형에서 사용되는 Try 패턴과 일치합니다.
서명은 다음과 같습니다 (.NET 4.7.2 이상에 있음).
//
// Summary:
// Searches the set for a given value and returns the equal value it finds, if any.
//
// Parameters:
// equalValue:
// The value to search for.
//
// actualValue:
// The value from the set that the search found, or the default value of T when
// the search yielded no match.
//
// Returns:
// A value indicating whether the search was successful.
public bool TryGetValue(T equalValue, out T actualValue);
추신 : 관심이 있으시면 앞으로 추가 할 관련 기능이 있습니다 -HashSet.GetOrAdd (T).
이것은 실제로 컬렉션 세트에서 큰 누락입니다. 키 사전 또는 객체 참조 검색을 허용하는 HashSet이 필요합니다. 너무 많은 사람들이 그것을 요구 해왔고, 왜 그것이 고쳐지지 않는지는 저를 넘어선 것입니다.
타사 라이브러리가 없으면 Dictionary<T, T>Dictionary가 항목을 해시 테이블로 저장하기 때문에 값과 동일한 키 를 사용하는 것이 가장 좋습니다 . 성능면에서는 HashSet과 동일하지만 물론 메모리를 낭비합니다 (항목 당 포인터 크기).
Dictionary<T, T> myHashedCollection;
...
if(myHashedCollection.ContainsKey[item])
item = myHashedCollection[item]; //replace duplicate
else
myHashedCollection.Add(item, item); //add previously unknown item
...
//work with unique item
이 메서드는 .NET Framework 4.7.2 (및 이전 .NET Core 2.0 )에 추가되었습니다. 참조하십시오 HashSet<T>.TryGetValue. 출처 인용 :
/// <summary>
/// Searches the set for a given value and returns the equal value it finds, if any.
/// </summary>
/// <param name="equalValue">The value to search for.
/// </param>
/// <param name="actualValue">
/// The value from the set that the search found, or the default value
/// of <typeparamref name="T"/> when the search yielded no match.</param>
/// <returns>A value indicating whether the search was successful.</returns>
/// <remarks>
/// This can be useful when you want to reuse a previously stored reference instead of
/// a newly constructed one (so that more sharing of references can occur) or to look up
/// a value that has more complete data than the value you currently have, although their
/// comparer functions indicate they are equal.
/// </remarks>
public bool TryGetValue(T equalValue, out T actualValue)
문자열 같음 비교자를 오버로드하는 것은 어떻습니까?
class StringEqualityComparer : IEqualityComparer<String>
{
public string val1;
public bool Equals(String s1, String s2)
{
if (!s1.Equals(s2)) return false;
val1 = s1;
return true;
}
public int GetHashCode(String s)
{
return s.GetHashCode();
}
}
public static class HashSetExtension
{
public static bool TryGetValue(this HashSet<string> hs, string value, out string valout)
{
if (hs.Contains(value))
{
valout=(hs.Comparer as StringEqualityComparer).val1;
return true;
}
else
{
valout = null;
return false;
}
}
}
그런 다음 HashSet을 다음과 같이 선언하십시오.
HashSet<string> hs = new HashSet<string>(new StringEqualityComparer());
또 다른 트릭은 InternalIndexOfHashSet 의 내부 기능에 액세스하여 Reflection을 수행 합니다. 필드 이름은 하드 코딩되므로 향후 .NET 버전에서 변경되면 중단됩니다. 다음 솔루션은 하나의 특정 유형 (예 : 문자열) 만 지원하지만 일반화 할 수도 있습니다.
public static class Extensions
{
private static Func<HashSet<string>, string, string> getHashSetInternalValue;
static Extensions()
{
ParameterExpression targetExp = Expression.Parameter(typeof(HashSet<string>), "target");
ParameterExpression itemExp = Expression.Parameter(typeof(string), "item");
var slotsExp = Expression.Field(targetExp, typeof(HashSet<string>).GetField("m_slots", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance));
var indexExp = Expression.Call(targetExp, typeof(HashSet<string>).GetMethod("InternalIndexOf", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance), itemExp);
var slotExp = Expression.ArrayAccess(slotsExp, indexExp);
var valueExp = Expression.Field(slotExp, "value");
var testExp = Expression.GreaterThanOrEqual(indexExp, Expression.Constant(0));
var conditionExp = Expression.Condition(testExp, valueExp, Expression.Constant(null, typeof(string)));
getHashSetInternalValue = Expression.Lambda<Func<HashSet<string>, string, string>>(conditionExp, new[] { targetExp, itemExp }).Compile();
}
/// <summary>
/// Gets the internal item value equal to <paramref name="item"/> or null if <paramref name="item"/> is not contained
/// </summary>
public static string GetInternalValue(this HashSet<string> hashet, string item)
{
return getHashSetInternalValue(hashet, item);
}
}
테스트:
var set = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { "TABLE" };
var intern = set.GetInternalValue("table");
Console.WriteLine(intern); // prints "TABLE"
자, 이렇게 할 수 있습니다
YourObject x = yourHashSet.Where(w => w.Name.Contains("strin")).FirstOrDefault();
선택한 개체의 새 인스턴스를 가져 오는 것입니다. 개체를 업데이트하려면 다음을 사용해야합니다.
yourHashSet.Where(w => w.Name.Contains("strin")).FirstOrDefault().MyProperty = "something";
이제 .NET Core 2.0에는이 정확한 방법이 있습니다.
HashSet.TryGetValue (T, T) 메서드
SortedSet은 옵션을 사용하는 경우 해당 상황에서 O (log n) 조회 시간을 가질 수 있습니다. 여전히 O (1)은 아니지만 적어도 더 좋습니다.
@ mp666 응답의 구현을 수정하여 모든 유형의 HashSet에 사용할 수 있으며 기본 같음 비교자를 재정의 할 수 있습니다.
public interface IRetainingComparer<T> : IEqualityComparer<T>
{
T Key { get; }
void ClearKeyCache();
}
/// <summary>
/// An <see cref="IEqualityComparer{T}"/> that retains the last key that successfully passed <see cref="IEqualityComparer{T}.Equals(T,T)"/>.
/// This class relies on the fact that <see cref="HashSet{T}"/> calls the <see cref="IEqualityComparer{T}.Equals(T,T)"/> with the first parameter
/// being an existing element and the second parameter being the one passed to the initiating call to <see cref="HashSet{T}"/> (eg. <see cref="HashSet{T}.Contains(T)"/>).
/// </summary>
/// <typeparam name="T">The type of object being compared.</typeparam>
/// <remarks>This class is thread-safe but may should not be used with any sort of parallel access (PLINQ).</remarks>
public class RetainingEqualityComparerObject<T> : IRetainingComparer<T> where T : class
{
private readonly IEqualityComparer<T> _comparer;
[ThreadStatic]
private static WeakReference<T> _retained;
public RetainingEqualityComparerObject(IEqualityComparer<T> comparer)
{
_comparer = comparer;
}
/// <summary>
/// The retained instance on side 'a' of the <see cref="Equals"/> call which successfully met the equality requirement agains side 'b'.
/// </summary>
/// <remarks>Uses a <see cref="WeakReference{T}"/> so unintended memory leaks are not encountered.</remarks>
public T Key
{
get
{
T retained;
return _retained == null ? null : _retained.TryGetTarget(out retained) ? retained : null;
}
}
/// <summary>
/// Sets the retained <see cref="Key"/> to the default value.
/// </summary>
/// <remarks>This should be called prior to performing an operation that calls <see cref="Equals"/>.</remarks>
public void ClearKeyCache()
{
_retained = _retained ?? new WeakReference<T>(null);
_retained.SetTarget(null);
}
/// <summary>
/// Test two objects of type <see cref="T"/> for equality retaining the object if successful.
/// </summary>
/// <param name="a">An instance of <see cref="T"/>.</param>
/// <param name="b">A second instance of <see cref="T"/> to compare against <paramref name="a"/>.</param>
/// <returns>True if <paramref name="a"/> and <paramref name="b"/> are equal, false otherwise.</returns>
public bool Equals(T a, T b)
{
if (!_comparer.Equals(a, b))
{
return false;
}
_retained = _retained ?? new WeakReference<T>(null);
_retained.SetTarget(a);
return true;
}
/// <summary>
/// Gets the hash code value of an instance of <see cref="T"/>.
/// </summary>
/// <param name="o">The instance of <see cref="T"/> to obtain a hash code from.</param>
/// <returns>The hash code value from <paramref name="o"/>.</returns>
public int GetHashCode(T o)
{
return _comparer.GetHashCode(o);
}
}
/// <summary>
/// An <see cref="IEqualityComparer{T}"/> that retains the last key that successfully passed <see cref="IEqualityComparer{T}.Equals(T,T)"/>.
/// This class relies on the fact that <see cref="HashSet{T}"/> calls the <see cref="IEqualityComparer{T}.Equals(T,T)"/> with the first parameter
/// being an existing element and the second parameter being the one passed to the initiating call to <see cref="HashSet{T}"/> (eg. <see cref="HashSet{T}.Contains(T)"/>).
/// </summary>
/// <typeparam name="T">The type of object being compared.</typeparam>
/// <remarks>This class is thread-safe but may should not be used with any sort of parallel access (PLINQ).</remarks>
public class RetainingEqualityComparerStruct<T> : IRetainingComparer<T> where T : struct
{
private readonly IEqualityComparer<T> _comparer;
[ThreadStatic]
private static T _retained;
public RetainingEqualityComparerStruct(IEqualityComparer<T> comparer)
{
_comparer = comparer;
}
/// <summary>
/// The retained instance on side 'a' of the <see cref="Equals"/> call which successfully met the equality requirement agains side 'b'.
/// </summary>
public T Key => _retained;
/// <summary>
/// Sets the retained <see cref="Key"/> to the default value.
/// </summary>
/// <remarks>This should be called prior to performing an operation that calls <see cref="Equals"/>.</remarks>
public void ClearKeyCache()
{
_retained = default(T);
}
/// <summary>
/// Test two objects of type <see cref="T"/> for equality retaining the object if successful.
/// </summary>
/// <param name="a">An instance of <see cref="T"/>.</param>
/// <param name="b">A second instance of <see cref="T"/> to compare against <paramref name="a"/>.</param>
/// <returns>True if <paramref name="a"/> and <paramref name="b"/> are equal, false otherwise.</returns>
public bool Equals(T a, T b)
{
if (!_comparer.Equals(a, b))
{
return false;
}
_retained = a;
return true;
}
/// <summary>
/// Gets the hash code value of an instance of <see cref="T"/>.
/// </summary>
/// <param name="o">The instance of <see cref="T"/> to obtain a hash code from.</param>
/// <returns>The hash code value from <paramref name="o"/>.</returns>
public int GetHashCode(T o)
{
return _comparer.GetHashCode(o);
}
}
/// <summary>
/// Provides TryGetValue{T} functionality similar to that of <see cref="IDictionary{TKey,TValue}"/>'s implementation.
/// </summary>
public class ExtendedHashSet<T> : HashSet<T>
{
/// <summary>
/// This class is guaranteed to wrap the <see cref="IEqualityComparer{T}"/> with one of the <see cref="IRetainingComparer{T}"/>
/// implementations so this property gives convenient access to the interfaced comparer.
/// </summary>
private IRetainingComparer<T> RetainingComparer => (IRetainingComparer<T>)Comparer;
/// <summary>
/// Creates either a <see cref="RetainingEqualityComparerStruct{T}"/> or <see cref="RetainingEqualityComparerObject{T}"/>
/// depending on if <see cref="T"/> is a reference type or a value type.
/// </summary>
/// <param name="comparer">(optional) The <see cref="IEqualityComparer{T}"/> to wrap. This will be set to <see cref="EqualityComparer{T}.Default"/> if none provided.</param>
/// <returns>An instance of <see cref="IRetainingComparer{T}"/>.</returns>
private static IRetainingComparer<T> Create(IEqualityComparer<T> comparer = null)
{
return (IRetainingComparer<T>) (typeof(T).IsValueType ?
Activator.CreateInstance(typeof(RetainingEqualityComparerStruct<>)
.MakeGenericType(typeof(T)), comparer ?? EqualityComparer<T>.Default)
:
Activator.CreateInstance(typeof(RetainingEqualityComparerObject<>)
.MakeGenericType(typeof(T)), comparer ?? EqualityComparer<T>.Default));
}
public ExtendedHashSet() : base(Create())
{
}
public ExtendedHashSet(IEqualityComparer<T> comparer) : base(Create(comparer))
{
}
public ExtendedHashSet(IEnumerable<T> collection) : base(collection, Create())
{
}
public ExtendedHashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer) : base(collection, Create(comparer))
{
}
/// <summary>
/// Attempts to find a key in the <see cref="HashSet{T}"/> and, if found, places the instance in <paramref name="original"/>.
/// </summary>
/// <param name="value">The key used to search the <see cref="HashSet{T}"/>.</param>
/// <param name="original">
/// The matched instance from the <see cref="HashSet{T}"/> which is not neccessarily the same as <paramref name="value"/>.
/// This will be set to null for reference types or default(T) for value types when no match found.
/// </param>
/// <returns>True if a key in the <see cref="HashSet{T}"/> matched <paramref name="value"/>, False if no match found.</returns>
public bool TryGetValue(T value, out T original)
{
var comparer = RetainingComparer;
comparer.ClearKeyCache();
if (Contains(value))
{
original = comparer.Key;
return true;
}
original = default(T);
return false;
}
}
public static class HashSetExtensions
{
/// <summary>
/// Attempts to find a key in the <see cref="HashSet{T}"/> and, if found, places the instance in <paramref name="original"/>.
/// </summary>
/// <param name="hashSet">The instance of <see cref="HashSet{T}"/> extended.</param>
/// <param name="value">The key used to search the <see cref="HashSet{T}"/>.</param>
/// <param name="original">
/// The matched instance from the <see cref="HashSet{T}"/> which is not neccessarily the same as <paramref name="value"/>.
/// This will be set to null for reference types or default(T) for value types when no match found.
/// </param>
/// <returns>True if a key in the <see cref="HashSet{T}"/> matched <paramref name="value"/>, False if no match found.</returns>
/// <exception cref="ArgumentNullException">If <paramref name="hashSet"/> is null.</exception>
/// <exception cref="ArgumentException">
/// If <paramref name="hashSet"/> does not have a <see cref="HashSet{T}.Comparer"/> of type <see cref="IRetainingComparer{T}"/>.
/// </exception>
public static bool TryGetValue<T>(this HashSet<T> hashSet, T value, out T original)
{
if (hashSet == null)
{
throw new ArgumentNullException(nameof(hashSet));
}
if (hashSet.Comparer.GetType().IsInstanceOfType(typeof(IRetainingComparer<T>)))
{
throw new ArgumentException($"HashSet must have an equality comparer of type '{nameof(IRetainingComparer<T>)}' to use this functionality", nameof(hashSet));
}
var comparer = (IRetainingComparer<T>)hashSet.Comparer;
comparer.ClearKeyCache();
if (hashSet.Contains(value))
{
original = comparer.Key;
return true;
}
original = default(T);
return false;
}
}
HashSet에는 Contains (T) 메서드가 있습니다.
사용자 정의 비교 방법이 필요한 경우 IEqualityComparer 를 지정할 수 있습니다 (예 : 사람 객체를 저장하지만 동등성 비교를 위해 SSN 사용).
ToList () 메서드를 사용하여 인덱서를 적용 할 수도 있습니다.
HashSet<string> mySet = new HashSet();
mySet.Add("mykey");
string key = mySet.toList()[0];
참고 URL : https://stackoverflow.com/questions/7760364/how-to-retrieve-actual-item-from-hashsett
반응형
'IT TIP' 카테고리의 다른 글
| Subversion 저장소 버전을 찾는 방법은 무엇입니까? (0) | 2020.10.19 |
|---|---|
| 함수 템플릿을 부분적으로 전문화 할 수없는 이유는 무엇입니까? (0) | 2020.10.19 |
| localStorage.getItem ( 'item')이 localStorage.item 또는 localStorage [ 'item']보다 나은가요? (0) | 2020.10.19 |
| nginx : upstream에 연결하는 동안 connect () 실패 (111 : 연결 거부) (0) | 2020.10.19 |
| 'O'가 새 라인을 열기 전에 지연됩니까? (0) | 2020.10.19 |