- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
考虑以下数据集和质心。一共有7个人,两个均值有8个维度。它们按行主要顺序存储。
short dim = 8;
float centroids[] = {
0.223, 0.002, 0.223, 0.412, 0.334, 0.532, 0.244, 0.612,
0.742, 0.812, 0.817, 0.353, 0.325, 0.452, 0.837, 0.441
};
float data[] = {
0.314, 0.504, 0.030, 0.215, 0.647, 0.045, 0.443, 0.325,
0.731, 0.354, 0.696, 0.604, 0.954, 0.673, 0.625, 0.744,
0.615, 0.936, 0.045, 0.779, 0.169, 0.589, 0.303, 0.869,
0.275, 0.406, 0.003, 0.763, 0.471, 0.748, 0.230, 0.769,
0.903, 0.489, 0.135, 0.599, 0.094, 0.088, 0.272, 0.719,
0.112, 0.448, 0.809, 0.157, 0.227, 0.978, 0.747, 0.530,
0.908, 0.121, 0.321, 0.911, 0.884, 0.792, 0.658, 0.114
};
float dist = 0.0, dist_sqrt;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 7; j++)
{
float dist_sum = 0.0;
for(int k = 0; k < dim; k++)
{
dist = centroids[i * dim + k] - data[j * dim + k];
dist_sum += dist * dist;
}
dist_sqrt = sqrt(dist_sum);
// do something with the distance
std::cout << dist_sqrt << std::endl;
}
最佳答案
可以通过推力来完成。解释将如何参与其中,并且代码非常密集。
首先要进行的主要观察是,可以通过转换归约来完成核心操作。推力变换操作用于对 vector 进行元素减法(单个质心)并对每个结果进行平方,而归约法将结果相加在一起,以得出欧几里德距离的平方。此操作的起点是thrust::reduce_by_key
,但要正确地将数据呈现给reduce_by_key
会涉及很多。
通过从上方取每个结果的平方根来产生最终结果,为此,我们可以使用普通的thrust::transform
。
以上是完成所有工作的仅两行推力代码的摘要说明。但是,第一行具有相当大的复杂性。为了利用并行性,我采取的方法是实际上按顺序“布局”必要的 vector ,并呈现给reduce_by_key
。举一个简单的例子,假设我们有2个质心和4个个体,并且我们的维数是2。
centroid 0: C00 C01
centroid 1: C10 C11
individ 0: I00 I01
individ 1: I10 I11
individ 2: I20 I21
individ 3: I30 I31
C00 C01 C00 C01 C00 C01 C00 C01 C10 C11 C10 C11 C10 C11 C10 C11
I00 I01 I10 I11 I20 I21 I30 I31 I00 I01 I10 I11 I20 I21 I30 I31
reduce_by_key
,我们还需要生成键值来描绘 vector :
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
transform_iterator
的自定义仿函数,以对
I
和
C
vector 进行减法(和平方),为此将它们压缩在一起。 vector 的“布局”将使用带有附加自定义索引创建函子的置换迭代器动态创建,以帮助
I
和
C
中的每个复制模式。
I
)和data
(C
)的centr
与counting_iterator
内部的自定义索引函子相结合,以生成我们需要的索引序列。 transform_iterator
和I
vector ,通过C
(每个布局 vector 一个)对 vector 进行虚拟“布局”。 permutation_iterator
和I
vector 压缩在一起,以创建C
元组 vector (虚拟)。 <float, float>
,并在zip_iterator
(I-C)^2
)组合
transform_iterator
,将transform_iterator
与自定义密钥生成函子结合在一起,以生成密钥序列(虚拟)counting_iterator
作为要减少的输入(键,值)。 reduce_by_key
的输出 vector 也是键和值。我们不需要密钥,因此我们将使用reduce_by_key
转储这些密钥。我们将保存的值。 #include <iostream>
#include <thrust/device_vector.h>
#include <thrust/host_vector.h>
#include <thrust/reduce.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/counting_iterator.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <thrust/copy.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>
#include <stdlib.h>
#define MAX_DATA 100000000
#define MAX_CENT 5000
#define TOL 0.001
unsigned long long dtime_usec(unsigned long long prev){
#define USECPSEC 1000000ULL
timeval tv1;
gettimeofday(&tv1,0);
return ((tv1.tv_sec * USECPSEC)+tv1.tv_usec) - prev;
}
unsigned verify(float *d1, float *d2, int len){
unsigned pass = 1;
for (int i = 0; i < len; i++)
if (fabsf(d1[i] - d2[i]) > TOL){
std::cout << "mismatch at: " << i << " val1: " << d1[i] << " val2: " << d2[i] << std::endl;
pass = 0;
break;}
return pass;
}
void eucl_dist_cpu(const float *centroids, const float *data, float *rdist, int num_centroids, int dim, int num_data, int print){
int out_idx = 0;
float dist, dist_sqrt;
for(int i = 0; i < num_centroids; i++)
for(int j = 0; j < num_data; j++)
{
float dist_sum = 0.0;
for(int k = 0; k < dim; k++)
{
dist = centroids[i * dim + k] - data[j * dim + k];
dist_sum += dist * dist;
}
dist_sqrt = sqrt(dist_sum);
// do something with the distance
rdist[out_idx++] = dist_sqrt;
if (print) std::cout << dist_sqrt << ", ";
}
if (print) std::cout << std::endl;
}
struct dkeygen : public thrust::unary_function<int, int>
{
int dim;
int numd;
dkeygen(const int _dim, const int _numd) : dim(_dim), numd(_numd) {};
__host__ __device__ int operator()(const int val) const {
return (val/dim);
}
};
typedef thrust::tuple<float, float> mytuple;
struct my_dist : public thrust::unary_function<mytuple, float>
{
__host__ __device__ float operator()(const mytuple &my_tuple) const {
float temp = thrust::get<0>(my_tuple) - thrust::get<1>(my_tuple);
return temp*temp;
}
};
struct d_idx : public thrust::unary_function<int, int>
{
int dim;
int numd;
d_idx(int _dim, int _numd) : dim(_dim), numd(_numd) {};
__host__ __device__ int operator()(const int val) const {
return (val % (dim*numd));
}
};
struct c_idx : public thrust::unary_function<int, int>
{
int dim;
int numd;
c_idx(int _dim, int _numd) : dim(_dim), numd(_numd) {};
__host__ __device__ int operator()(const int val) const {
return (val % dim) + (dim * (val/(dim*numd)));
}
};
struct my_sqrt : public thrust::unary_function<float, float>
{
__host__ __device__ float operator()(const float val) const {
return sqrtf(val);
}
};
unsigned long long eucl_dist_thrust(thrust::host_vector<float> ¢roids, thrust::host_vector<float> &data, thrust::host_vector<float> &dist, int num_centroids, int dim, int num_data, int print){
thrust::device_vector<float> d_data = data;
thrust::device_vector<float> d_centr = centroids;
thrust::device_vector<float> values_out(num_centroids*num_data);
unsigned long long compute_time = dtime_usec(0);
thrust::reduce_by_key(thrust::make_transform_iterator(thrust::make_counting_iterator<int>(0), dkeygen(dim, num_data)), thrust::make_transform_iterator(thrust::make_counting_iterator<int>(dim*num_data*num_centroids), dkeygen(dim, num_data)),thrust::make_transform_iterator(thrust::make_zip_iterator(thrust::make_tuple(thrust::make_permutation_iterator(d_centr.begin(), thrust::make_transform_iterator(thrust::make_counting_iterator<int>(0), c_idx(dim, num_data))), thrust::make_permutation_iterator(d_data.begin(), thrust::make_transform_iterator(thrust::make_counting_iterator<int>(0), d_idx(dim, num_data))))), my_dist()), thrust::make_discard_iterator(), values_out.begin());
thrust::transform(values_out.begin(), values_out.end(), values_out.begin(), my_sqrt());
cudaDeviceSynchronize();
compute_time = dtime_usec(compute_time);
if (print){
thrust::copy(values_out.begin(), values_out.end(), std::ostream_iterator<float>(std::cout, ", "));
std::cout << std::endl;
}
thrust::copy(values_out.begin(), values_out.end(), dist.begin());
return compute_time;
}
int main(int argc, char *argv[]){
int dim = 8;
int num_centroids = 2;
float centroids[] = {
0.223, 0.002, 0.223, 0.412, 0.334, 0.532, 0.244, 0.612,
0.742, 0.812, 0.817, 0.353, 0.325, 0.452, 0.837, 0.441
};
int num_data = 8;
float data[] = {
0.314, 0.504, 0.030, 0.215, 0.647, 0.045, 0.443, 0.325,
0.731, 0.354, 0.696, 0.604, 0.954, 0.673, 0.625, 0.744,
0.615, 0.936, 0.045, 0.779, 0.169, 0.589, 0.303, 0.869,
0.275, 0.406, 0.003, 0.763, 0.471, 0.748, 0.230, 0.769,
0.903, 0.489, 0.135, 0.599, 0.094, 0.088, 0.272, 0.719,
0.112, 0.448, 0.809, 0.157, 0.227, 0.978, 0.747, 0.530,
0.908, 0.121, 0.321, 0.911, 0.884, 0.792, 0.658, 0.114,
0.721, 0.555, 0.979, 0.412, 0.007, 0.501, 0.844, 0.234
};
std::cout << "cpu results: " << std::endl;
float dist[num_data*num_centroids];
eucl_dist_cpu(centroids, data, dist, num_centroids, dim, num_data, 1);
thrust::host_vector<float> h_data(data, data + (sizeof(data)/sizeof(float)));
thrust::host_vector<float> h_centr(centroids, centroids + (sizeof(centroids)/sizeof(float)));
thrust::host_vector<float> h_dist(num_centroids*num_data);
std::cout << "gpu results: " << std::endl;
eucl_dist_thrust(h_centr, h_data, h_dist, num_centroids, dim, num_data, 1);
float *data2, *centroids2, *dist2;
num_centroids = 10;
num_data = 1000000;
if (argc > 2) {
num_centroids = atoi(argv[1]);
num_data = atoi(argv[2]);
if ((num_centroids < 1) || (num_centroids > MAX_CENT)) {std::cout << "Num centroids out of range" << std::endl; return 1;}
if ((num_data < 1) || (num_data > MAX_DATA)) {std::cout << "Num data out of range" << std::endl; return 1;}
if (num_data * dim * num_centroids > 2000000000) {std::cout << "data set out of range" << std::endl; return 1;}}
std::cout << "Num Data: " << num_data << std::endl;
std::cout << "Num Cent: " << num_centroids << std::endl;
std::cout << "result size: " << ((num_data*num_centroids*4)/1048576) << " Mbytes" << std::endl;
data2 = new float[dim*num_data];
centroids2 = new float[dim*num_centroids];
dist2 = new float[num_data*num_centroids];
for (int i = 0; i < dim*num_data; i++) data2[i] = rand()/(float)RAND_MAX;
for (int i = 0; i < dim*num_centroids; i++) centroids2[i] = rand()/(float)RAND_MAX;
unsigned long long dtime = dtime_usec(0);
eucl_dist_cpu(centroids2, data2, dist2, num_centroids, dim, num_data, 0);
dtime = dtime_usec(dtime);
std::cout << "cpu time: " << dtime/(float)USECPSEC << "s" << std::endl;
thrust::host_vector<float> h_data2(data2, data2 + (dim*num_data));
thrust::host_vector<float> h_centr2(centroids2, centroids2 + (dim*num_centroids));
thrust::host_vector<float> h_dist2(num_data*num_centroids);
dtime = dtime_usec(0);
unsigned long long ctime = eucl_dist_thrust(h_centr2, h_data2, h_dist2, num_centroids, dim, num_data, 0);
dtime = dtime_usec(dtime);
std::cout << "gpu total time: " << dtime/(float)USECPSEC << "s, gpu compute time: " << ctime/(float)USECPSEC << "s" << std::endl;
if (!verify(dist2, &(h_dist2[0]), num_data*num_centroids)) {std::cout << "Verification failure." << std::endl; return 1;}
std::cout << "Success!" << std::endl;
return 0;
}
discard_iterator
的乘积小于20亿的数据集。但是,当您接近这个数字时,您将需要同时具有几GB内存的GPU和CPU。我简要探讨了更大的数据集大小。从(例如)扩展到各个地方都需要进行一些代码更改。 dimension*number_of_centroids*number_of_individuals
到int
等。但是,由于我仍在研究该代码的问题,因此我没有提供。 关于c++ - 推力 vector 距离计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27823951/
A是不同元素的序列,B是A的子序列,A-B是A中的所有元素,但不是B中的所有元素距离(A) = 总和|a(i)-a(i+1)|从 i=1 到 n-1找到一个子序列 B 使得 Dist(B)+Dist(
我想通过计算每对中所有(多维)点集之间距离的平均值来量化组相似性。 我可以很容易地手动为每对组手动完成此操作,如下所示: library(dplyr) library(tibble) library(
在 OpenXML 中用于指定大小或 X、Y 坐标的度量单位是什么? (介绍)。 将那些与像素匹配是否有意义,如果是这样,那些如何转换为像素? graphicFrame.Transform = new
我想知道是否有人可以帮助我替换过渡层中的值。 如果我尝试: transitionlayer[transitionlayer >= 0.14] = 0.14 : comparison (5) is
我在 firebase 中有一个列表,其中包括地理位置(经度和纬度),并且我想获得距给定坐标最近的 10 个位置。 我正在从 MySQL 过渡,在那里我将计算 SELECT 中的距离, 并在 ORDE
如何在 Python 中根据 2 个 GPS 坐标计算速度、距离和方向(度)?每个点都有纬度、经度和时间。 我在这篇文章中找到了半正矢距离计算: Calculate distance between
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 6 年前。 Improve this ques
我只想使用 matplotlib 标记两条曲线之间发生最大偏差的位置。请帮助我。 垂直距离适用于 Kolmogorov–Smirnov test import numpy as np %matplot
我有一个包含数万行重复项的文件。我想根据行号找到重复项之间的平均时间/距离。 例如:(其中第一列是行号) 1 string1 2 string2 3 string2 4 string1 5 strin
用公式speed=distance/time计算时间 但时间总是0我的输入是 distance=10 和 speed=5 我的输出必须 = 2 #include int main() { in
我正在使用 Levenshtein 算法来查找两个字符串之间的相似性。这是我正在制作的程序的一个非常重要的部分,因此它需要有效。问题是该算法没有发现以下示例相似: CONAIR AIRCON 算法给出
对于一个房地产网站,我需要实现一个允许搜索文本和距离的搜索机制。 当 lat 和 lon 记录在单独的列中时,在 MySQL 表上进行距离计算很容易,但房子往往有 LOT true/false 属性。
是否可以在触发前更改 UIPanGestureRecognizer 的距离?目前的实现似乎在触发前有 5-10 像素的距离余量,我想降低它如果可能的话。 原因是我将 UIPanGestureRecog
我试图找到两个网格之间的偏差。例如在 3d 空间中定义的两组点之间的差异,我计划使用一些 3d 可视化工具来可视化距离,例如QT3d 或一些基于开放式 gl 的库。 我有两组网格,基本上是两个 .ST
所以,我有这个函数可以快速返回两个字符串之间的 Levenshtein 距离: Function Levenshtein(ByVal string1 As String, ByVal string2
我正在尝试用字典创建一个光学字符识别系统。 事实上,我还没有实现字典=) 我听说有一些基于 Levenstein 距离的简单指标,这些指标考虑了不同符号之间的不同距离。例如。 'N' 和 'H' 彼此
我在PostGIS数据库(-4326)中使用经纬度/经度SRID。我想以一种有效的方式找到最接近给定点的点。我试图做一个 ORDER BY ST_Distance(point, ST_GeomF
我想从线串的一端开始提取沿线串已知距离处的点的坐标。 例如: library(sf) path % group_by(L1) %>% summarise(do_union =
我已经编写了这些用于聚类基于序列的数据的函数: library(TraMineR) library(cluster) clustering <- function(data){ data <- s
是否可以设置 UILabel 的行之间的距离,因为我有一个 UILabel 包含 3 行,并且换行模式是自动换行? 最佳答案 如果您指的是“前导”,它指的是类型行之间的间隙 - 您无法在 UILabe
我是一名优秀的程序员,十分优秀!