java - الحفاظ على ArrayList من صفائف فريدة من نوعها في جافا




(5)

كانت هناك بالفعل بعض الإجابات ، لكن بعضها يقدم بعض الافتراضات التي لا يمكن استخلاصها من السؤال ، والبعض الآخر يقترح تغييرات معينة يمكن اعتبارها حلولاً ، والبعض الآخر له عيوب معينة يجب عدم تجاهلها.

مخاطبة البعض منهم هنا:

  • يؤدي تغيير العناصر إلى Set<Integer> إلى افتراض أن كل عنصر قد يظهر مرة واحدة فقط. بالإضافة إلى ذلك ، إذا كان الكود الموجود بالفعل ينشئ المصفوفات int[] ، وكان الكود المتلقين للمعلومات يحتاج إلى المصفوفات int[] ، فإن استخدام بنية البيانات الناتجة سيكون خرقاء:

    int array[] = somewhere.getArray();
    Set<Integer> set = convert(array); // Convert array to set
    data.add(set);
    ...
    set = data.iterator().next();
    array = convert(set);              // Convert set to array
    somewhere.setArray(array);

    اعتمادًا على حجم المصفوفات ، قد يكون لهذا تأثير على الأداء وتوليد بعض الذاكرة الزائدة.

  • يبدو استخدام TreeSet<int[]> حلاً بسيطًا ومعقولًا. أجمل شيء هو أنه يمكن أن يخزن مباشرة صفائف int[] . ولكن لديها بعض العيوب:

    1. أنه ينطوي على الطلب. لم يعد من الممكن استخدام تطبيق Set آخر (مثل LinkedHashSet ) يحتفظ بترتيب الإدراج
    2. قد يكون من الصعب بعض الشيء تنفيذ المقارنة بطريقة تتوافق مع equals ، والفشل في القيام بذلك سيؤدي إلى عدم إطاعة المجموعة للعقد العام لواجهة Set
    3. من المحتمل أن يتضمن التنفيذ البسيط والصحيح للمقارنة فرز المصفوفات. وهذا يعني أن المصفوفات قد يتعين تعديلها إما عن طريق إدخالها في المجموعة ، وهو أمر غير مقبول بالتأكيد ، أو يتعين على المرء إنشاء نسخ دفاعية من المصفوفات. هنا ، يجب على المرء أن يضع في الاعتبار أنه يجب القيام بالنسخة والفرز في كل مرة يتم فيها إضافة مجموعة جديدة ، ويجب أن يتم ذلك عدة مرات أثناء النزول إلى الشجرة. على الرغم من أن عدد المقارنات سيكون O (log (n)) لمجموعة ذات عناصر n ، فإن الفرز سيستغرق O (m log (m)) في كل مرة للصفائف ذات الطول m ، والتي قد تكون باهظة الثمن.
  • يمكن تطبيق وسيطات مماثلة للطرق التي تتحقق مما إذا كان هناك صفيف "مكافئ" موجود بالفعل قبل إدراج واحدة جديدة. بالإضافة إلى ذلك ، لا تعتمد هذه الطرق على بنية البيانات ، ولكن يجب أن تكون جزءًا من التعليمات البرمجية التي تستخدم بنية البيانات.

لهذه الأسباب ، سأذهب إلى مقاربة تشبه بشكل أساسي النهج الذي ذكره ميخائيل موسكورا في إجابته : إنه يستند إلى فصل يلف ببساطة المصفوفات int[] معينة int[] ، وينفذ equals و hashCode وفقًا لذلك.

(لاحظ أنه يمكنك أيضًا السماح لهذه الفئة بتنفيذ Comparable ، مع إضافة بعض المرونة حول ما إذا كان يمكن وضعها في TreeSet ، إذا كنت على دراية بالصعوبات والعيوب المحتملة المذكورة أعلاه ...)

في المثال أدناه ، تسمى هذه الفئة UnorderedIntArray . من الناحية النظرية ، سيكون من المفضل أن يكون لديك Set<int[]> ، والحل أدناه يجب أن يستخدم Set<UnorderedIntArray> . ولكن نظرًا لأن هذه الفئة لا تلتف إلا بمصفوفة موجودة ، فإن حمل الذاكرة والذاكرة يكون صفرًا تقريبًا ، ولذا ما زلت أعتبره مفيدًا مقارنةً بالتحويل بين int[] وبعض أنواع البيانات الأخرى. لاحظ أيضًا أن طريقة equals في المثال أدناه ليست فعالة للغاية ، ولكنها طريقة بسيطة لضمان الامتثال لعقود equals .

import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class UniqueArraysTest {

    public static void main(String[] args) {
        Set<UnorderedIntArray> result = new LinkedHashSet<>();
        int[] x = { 1, 2, 3 };
        int[] y = { 2, 1, 3 };
        int[] z = { 2, 1, 3 };

        int[] u = { 1, 1, 1, 2, 3 };
        int[] v = { 1, 1, 1, 2, 3 };
        int[] w = { 1, 1, 1, 1, 3 };

        result.add(new UnorderedIntArray(x));
        result.add(new UnorderedIntArray(y));
        result.add(new UnorderedIntArray(z));
        result.add(new UnorderedIntArray(u));
        result.add(new UnorderedIntArray(v));
        result.add(new UnorderedIntArray(w));

        for (UnorderedIntArray a : result) {
            int[] array = a.getArray();
            System.out.println(Arrays.toString(array));
        }

    }

    static class UnorderedIntArray {
        private final int array[];

        UnorderedIntArray(int array[]) {
            this.array = array;
        }

        int[] getArray() {
            return array;
        }

        @Override
        public int hashCode() {
            return IntStream.of(array).sum();
        }

        @Override
        public boolean equals(Object object) {
            if (object == this) {
                return true;
            }
            if (object == null) {
                return false;
            }
            if (!(object instanceof UnorderedIntArray)) {
                return false;
            }
            UnorderedIntArray that = (UnorderedIntArray)object;
            if (this.array.length != that.array.length) {
                return false;
            }
            // This is very simple, but not very efficient. More efficient
            // solutions could be implemented, but they are not trivial...
            Map<Integer, Long> thisFrequencies = computeFrequencies(this.array);
            Map<Integer, Long> thatFrequencies = computeFrequencies(that.array);
            return thisFrequencies.equals(thatFrequencies);
        }

        private Map<Integer, Long> computeFrequencies(int array[]) {
            return Arrays.stream(array).boxed().collect(
                Collectors.groupingBy(Function.identity(), Collectors.counting()));
        }

        @Override
        public String toString() {
            return Arrays.toString(array);
        }

    }
}

لإدخال

int[] x = { 1, 2, 3 };
int[] y = { 2, 1, 3 };
int[] z = { 2, 1, 3 };
int[] u = { 1, 1, 1, 2, 3 };
int[] v = { 1, 1, 1, 2, 3 };
int[] w = { 1, 1, 1, 1, 3 };

الإخراج هو المتوقع

[1, 2, 3]
[1, 1, 1, 2, 3]
[1, 1, 1, 1, 3]

كيف يمكنني الحفاظ على ArrayList من المصفوفات الفريدة؟

على سبيل المثال ، إذا كان لدي المصفوفات التالية:

int [] a = {1,2,3};
int [] b = {2,1,3};
int [] c = {2,1,3};

وفقا لمنطقي أنا أفكر في مجموعات فريدة من نوعها. لذلك في الحالة أعلاه a = b = c لأنها تحتوي جميعًا على "1" ، "2" ، "3" .

من الناحية المثالية ، أتساءل عما إذا كان هناك بنية بيانات في Java تتعرف على ذلك.

حاولت ما يلي:

Set<int []> result = new LinkedHashSet<>();
int [] x = {1,2,3};
int [] z = {2,1,3};
int [] m = {2,1,3};

result.add(x);
result.add(z);
result.add(m);

for(int [] arr: result){
    printArray(arr);
}

مخرجاتي كانت:

1 2 3
2 1 3
2 1 3

من الناحية المثالية ، أود أن يطبع مخرجاتي واحدة فقط من المجموعات أعلاه.


ما يبدو أنك تريده هو مجموعة من الأعداد الصحيحة ، وإذا كان الترتيب النسبي مهم بالنسبة لك ، فيمكنك استخدام شيء مثل هذا:

import java.util.Set;
import java.util.LinkedHashSet;
import java.util.Arrays;
import java.util.stream.Collectors;

public class HelloWorld
{
  public static void main(String[] args)
  {
        Set<Set<Integer>> result = new LinkedHashSet<>();
        int[] x = {1, 2, 3};
        int[] z = {2, 1, 3};
        int[] m = {2, 1, 3};

        result.add(Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(z).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));
        result.add(Arrays.stream(m).boxed().collect(Collectors.toCollection(LinkedHashSet::new)));

        System.out.println(result);
  }
}

يمكنك أيضًا استخراج Arrays.stream(x).boxed().collect(Collectors.toCollection(LinkedHashSet::new)) في وظيفة منفصلة.


يمكنك إنشاء طريقة لإضافتها إن لم تكن متساوية:

public static Set<int[]> addIfNotExist(Set<int[]> result, int[] array) {
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                Arrays.sort(array);
                return Arrays.equals(a, array);
            });
    if (check) {
        return result;
    } else {
        result.add(array);
        return result;
    }
}

ثم يمكنك استدعاء طريقتك مثل:

result = addIfNotExist(result, x);
result = addIfNotExist(result, z);
result = addIfNotExist(result, m);

انتاج |

[1, 2, 3]

أو إذا كنت تستخدم مجموعة ثابتة ، يمكنك فقط استخدام:

static Set<int[]> result = new LinkedHashSet<>();

public static void main(String[] args) {

    int[] x = {1, 2, 3};
    int[] z = {2, 1, 3};
    int[] m = {2, 1, 3};

    addIfNotExist(result, x);
    addIfNotExist(result, z);
    addIfNotExist(result, m);

    for (int[] arr : result) {
        System.out.println(Arrays.toString(arr));
    }
}

public static void addIfNotExist(Set<int[]> result, int[] array) {
    boolean check = result.stream()
            .anyMatch(a -> {
                Arrays.sort(a);
                Arrays.sort(array);
                return Arrays.equals(a, array);
            });
    if (!check) {
        result.add(array);
    }
}

يمكنك إنشاء فئة مجمعة تحتوي على متغير مثيل غير قابل للتغيير من صفيف صحيح وتجاوز رمز التجزئة:

public class ArrayWrapper {
   private final int[] a;

@Override
public int hashCode(){
 //your implementation 
}
@Override
 public boolean equals(){
  // your implementation 
 }
}

وبعد ذلك يمكنك استخدام:

Set<ArrayWrapper> set = new HashSet<>();

@Test
    public void testArraysSet() {
        Set<int[]> myArrays = new TreeSet<>((arr1, arr2) -> {
            Arrays.sort(arr1);
            Arrays.sort(arr2);
            return Arrays.equals(arr1, arr2) ? 0 : 1;
        });

        int [] a = {1,2,3};
        int [] b = {2,1,3};
        int [] c = {2,1,3};

        myArrays.add(a);
        myArrays.add(b);
        myArrays.add(c);

        assertEquals(1, myArrays.size());
    }

هذا ينبغي أن يفعل ، والفرز قد تبطئ الأمور قليلا على الرغم من. قد ترغب في النظر في مجموعة أسرع مقارنة.





arraylist