I think O(N^2)-like performance is unavoidable here Dave. However, although
Peter's algorithm is indeed O(N^2), it should be faster than Tagir's and
reasonable(-ish) in practice.
This is because the inner loop starts off not executing at all in the outer
loop's first iteration; and each time the outer loop iterates, the inner
loop's number of iterations increases by 1, eventually reaching N
iterations when the outer loop itself hits iteration N.
So although Peter's algorithm is O(N^2) in theory, in practice it shouldn't
or isn't as bad as most O(N^2) algos, since the number of steps it takes is
less than some ratio of N^2 for sufficiently large N.
On 11 September 2016 at 17:55, Dave Brosius <dbros...@mebigfatguy.com>
wrote:
> Sure, but both of those algorithms are n^2, which is a bit painful,
> especially given all the pointer chasing that occurs with iterators.
>
>
>
> On 09/11/2016 08:20 AM, Peter Levart wrote:
>
>> Hi,
>>
>> Even if the elements are not comparable, you could rely on the fact that
>> Collection(s) usually create iterators with stable iteration order, so you
>> could do the following:
>>
>>
>> Set<Integer> set = Set.of(1, 2, 3, 4);
>>
>> Iterator<Integer> it1 = set.iterator();
>> for (int n1 = 0; it1.hasNext(); n1++) {
>> Integer e1 = it1.next();
>> Iterator<Integer> it2 = set.iterator();
>> for (int n2 = 0; n2 < n1; n2++) {
>> Integer e2 = it2.next();
>> System.out.println(e1 + " <-> " + e2);
>> }
>> }
>>
>>
>> Regards, Peter
>>
>> On 09/11/2016 02:02 PM, Tagir F. Valeev wrote:
>>
>>> Hello!
>>>
>>> As your keys are comparable, you can create normal iterators and
>>> filter the results like this:
>>>
>>> for(String v1 : s) {
>>> for(String v2 : s) {
>>> if(v1.compareTo(v2) < 0) {
>>> System.out.println(v1 + " <-->" + v2);
>>> }
>>> }
>>> }
>>>
>>> Or using Stream API:
>>>
>>> s.stream().flatMap(v1 -> s.stream()
>>> .filter(v2 -> v1.compareTo(v2) < 0).map(v2 -> v1 + " <-->" + v2))
>>> .forEach(System.out::println);
>>>
>>> With best regards,
>>> Tagir Valeev.
>>>
>>>
>>> DB> It would be nice to be able to associate each element in a collection
>>> DB> with another element in the collection, which is something very
>>> easily
>>> DB> done with index based collections, but with sets, etc this isn't so
>>> DB> easy... unless i'm having a brainfart.
>>>
>>> DB> So i'd like to do this, but Iterator doesn't implement Cloneable...
>>> Any
>>> DB> reason not to? or is there another way that's missing me?
>>>
>>> DB> public class ItClone {
>>>
>>> DB> public static void main(String[] args) {
>>> DB> Set<String> s = Collections.newSetFromMap(new
>>> DB> ConcurrentHashMap<String, Boolean>());
>>>
>>> DB> s.add("Fee");
>>> DB> s.add("Fi");
>>> DB> s.add("Fo");
>>> DB> s.add("Fum");
>>>
>>> DB> Iterator<String> it1 = s.iterator();
>>> DB> while (it1.hasNext()) {
>>> DB> String v1 = it1.next();
>>>
>>> DB> Iterator<String> it2 = (Iterator<String>) it1.*clone*();
>>> DB> while (it2.hasNext()) {
>>> DB> String v2 = it2.next();
>>>
>>> DB> System.out.println(v1 + " <-->" + v2);
>>> DB> }
>>> DB> }
>>> DB> }
>>> DB> }
>>>
>>>
>>
>
