← Back to branch summary

~ubuntu-branches/ubuntu/vivid/elki/vivid

« back to all changes in this revision

Viewing changes to src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseMaximumDistanceFunction.java

  • Committer: Package Import Robot
  • Author(s): Erich Schubert
  • Date: 2014-01-22 16:23:20 UTC
  • mfrom: (1.1.8)
  • Revision ID: package-import@ubuntu.com-20140122162320-dtqtgcdiki8t9unc
Tags: 0.6.0-1
* New upstream final.
* 3DPC extension is not included, but may be uploaded as a separate
  package when there is actual need (it is a demo software, not meant
  for use outside of research, so just get the source code!)
* Upgrade to policy 3.9.5.0 (no changes)

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/de/lmu/ifi/dbs/elki/distance/distancefunction/minkowski/SparseMaximumDistanceFunction.java
1
1
package de.lmu.ifi.dbs.elki.distance.distancefunction.minkowski;
2
2
 
3
 
import java.util.BitSet;
4
 
 
5
 
import de.lmu.ifi.dbs.elki.data.SparseNumberVector;
6
 
import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
7
3
/*
8
4
 This file is part of ELKI:
9
5
 Environment for Developing KDD-Applications Supported by Index-Structures
26
22
 You should have received a copy of the GNU Affero General Public License
27
23
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
28
24
 */
 
25
import de.lmu.ifi.dbs.elki.data.SparseNumberVector;
 
26
import de.lmu.ifi.dbs.elki.utilities.optionhandling.AbstractParameterizer;
29
27
 
30
28
/**
31
29
 * Maximum distance function. Optimized for sparse vectors.
37
35
   * Static instance
38
36
   */
39
37
  public static final SparseMaximumDistanceFunction STATIC = new SparseMaximumDistanceFunction();
40
 
  
 
38
 
41
39
  /**
42
40
   * Constructor.
43
41
   * 
51
49
  @Override
52
50
  public double doubleDistance(SparseNumberVector<?> v1, SparseNumberVector<?> v2) {
53
51
    // Get the bit masks
54
 
    BitSet b1 = v1.getNotNullMask();
55
 
    BitSet b2 = v2.getNotNullMask();
56
 
    double accu = 0;
57
 
    int i1 = b1.nextSetBit(0);
58
 
    int i2 = b2.nextSetBit(0);
59
 
    while (true) {
60
 
      if (i1 == i2) {
61
 
        if (i1 < 0) {
62
 
          break;
63
 
        }
64
 
        // Both vectors have a value.
65
 
        double val = Math.abs(v1.doubleValue(i1) - v2.doubleValue(i2));
66
 
        accu = Math.max(accu, val);
67
 
        i1 = b1.nextSetBit(i1 + 1);
68
 
        i2 = b2.nextSetBit(i2 + 1);
69
 
      } else if (i2 < 0 || (i1 < i2 && i1 >= 0)) {
 
52
    double accu = 0.;
 
53
    int i1 = v1.iter(), i2 = v2.iter();
 
54
    while(v1.iterValid(i1) && v2.iterValid(i2)) {
 
55
      final int d1 = v1.iterDim(i1), d2 = v2.iterDim(i2);
 
56
      if(d1 < d2) {
70
57
        // In first only
71
 
        double val = Math.abs(v1.doubleValue(i1));
72
 
        accu = Math.max(accu, val);
73
 
        i1 = b1.nextSetBit(i1 + 1);
74
 
      } else {
 
58
        final double val = Math.abs(v1.iterDoubleValue(i1));
 
59
        if(val > accu) {
 
60
          accu = val;
 
61
        }
 
62
        i1 = v1.iterAdvance(i1);
 
63
      }
 
64
      else if(d2 < d1) {
75
65
        // In second only
76
 
        double val = Math.abs(v2.doubleValue(i2));
77
 
        accu = Math.max(accu, val);
78
 
        i2 = b2.nextSetBit(i2 + 1);
79
 
      }
 
66
        final double val = Math.abs(v2.iterDoubleValue(i2));
 
67
        if(val > accu) {
 
68
          accu = val;
 
69
        }
 
70
        i2 = v2.iterAdvance(i2);
 
71
      }
 
72
      else {
 
73
        // Both vectors have a value.
 
74
        final double val = Math.abs(v1.iterDoubleValue(i1) - v2.iterDoubleValue(i2));
 
75
        if(val > accu) {
 
76
          accu = val;
 
77
        }
 
78
        i1 = v1.iterAdvance(i1);
 
79
        i2 = v2.iterAdvance(i2);
 
80
      }
 
81
    }
 
82
    while(v1.iterValid(i1)) {
 
83
      // In first only
 
84
      final double val = Math.abs(v1.iterDoubleValue(i1));
 
85
      if(val > accu) {
 
86
        accu = val;
 
87
      }
 
88
      i1 = v1.iterAdvance(i1);
 
89
    }
 
90
    while(v2.iterValid(i2)) {
 
91
      // In second only
 
92
      final double val = Math.abs(v2.iterDoubleValue(i2));
 
93
      if(val > accu) {
 
94
        accu = val;
 
95
      }
 
96
      i2 = v2.iterAdvance(i2);
80
97
    }
81
98
    return accu;
82
99
  }
83
100
 
84
101
  @Override
85
102
  public double doubleNorm(SparseNumberVector<?> v1) {
86
 
    double sqrDist = 0;
87
 
    // Get the bit masks
88
 
    BitSet b1 = v1.getNotNullMask();
89
 
    // Set in first only
90
 
    for(int i = b1.nextSetBit(0); i >= 0; i = b1.nextSetBit(i + 1)) {
91
 
      sqrDist = Math.max(sqrDist, Math.abs(v1.doubleValue(i)));
 
103
    double accu = 0.;
 
104
    for(int it = v1.iter(); v1.iterValid(it); it = v1.iterAdvance(it)) {
 
105
      final double val = Math.abs(v1.iterDoubleValue(it));
 
106
      if(val > accu) {
 
107
        accu = val;
 
108
      }
92
109
    }
93
 
    return sqrDist;
 
110
    return accu;
94
111
  }
95
112
 
96
113
  /**