C++, score: 5990, O([2NlogN]/3)
This implementation uses a binary tree look up table. My first implementation was O(NlogN), but a last minute optimization, which looks up the product of all array elements minus a pair, + 2 multiplications saved the day. I think this could still be optimized a bit further, maybe another 16%...
I've left some debugging traces in, only because it's easier to delete them than to rewrite them :)
[Edit] the actual complexity is measured at O([2NlogN]/3) for 100. It is actually a bit worse than O(NlogN) for small sets, but tends towards O([NlogN]/2) as the array grows very large O(0.57.NlogN) for a a set of 1 million elements.
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <random>
#include <cstdlib>
using DataType = long double;
using DataVector = std::vector<DataType>;
struct ProductTree
{
std::vector<DataVector> tree_;
size_t ops_{ 0 };
ProductTree(const DataVector& v) : ProductTree(v.begin(), v.end()) {}
ProductTree(DataVector::const_iterator first, DataVector::const_iterator last)
{
Build(first, last);
}
void Build(DataVector::const_iterator first, DataVector::const_iterator last)
{
tree_.emplace_back(DataVector(first, last));
auto size = std::distance(first, last);
for (auto n = size; n >= 2; n >>= 1)
{
first = tree_.back().begin();
last = tree_.back().end();
DataVector v;
v.reserve(n);
while (first != last) // steps in pairs
{
auto x = *(first++);
if (first != last)
{
++ops_;
x *= *(first++); // could optimize this out,small gain
}
v.push_back(x);
}
tree_.emplace_back(v);
}
}
// O(NlogN) implementation...
DataVector Prod()
{
DataVector result(tree_[0].size());
for (size_t i = 0; i < tree_[0].size(); ++i)
{
auto depth = tree_.size() - 1;
auto k = i >> depth;
result[i] = ProductAtDepth(i, depth);
}
return result;
}
DataType ProductAtDepth(size_t index, size_t depth)
{
if (depth == 0)
{
return ((index ^ 1) < tree_[depth].size())
? tree_[depth][index ^ 1]
: 1;
}
auto k = (index >> depth) ^ 1;
if ((k < tree_[depth].size()))
{
++ops_;
return tree_[depth][k] * ProductAtDepth(index, depth - 1);
}
return ProductAtDepth(index, depth - 1);
}
// O([3NlogN]/2) implementation...
DataVector Prod2()
{
DataVector result(tree_[0].size());
for (size_t i = 0; i < tree_[0].size(); ++i) // steps in pairs
{
auto depth = tree_.size() - 1;
auto k = i >> depth;
auto x = ProductAtDepth2(i, depth);
if (i + 1 < tree_[0].size())
{
ops_ += 2;
result[i + 1] = tree_[0][i] * x;
result[i] = tree_[0][i + 1] * x;
++i;
}
else
{
result[i] = x;
}
}
return result;
}
DataType ProductAtDepth2(size_t index, size_t depth)
{
if (depth == 1)
{
index = (index >> 1) ^ 1;
return (index < tree_[depth].size())
? tree_[depth][index]
: 1;
}
auto k = (index >> depth) ^ 1;
if ((k < tree_[depth].size()))
{
++ops_;
return tree_[depth][k] * ProductAtDepth2(index, depth - 1);
}
return ProductAtDepth2(index, depth - 1);
}
};
int main()
{
//srand(time());
DataVector data;
for (int i = 0; i < 1000; ++i)
{
auto x = rand() & 0x3; // avoiding overflow and zero vaolues for testing
data.push_back((x) ? x : 1);
}
//for (int i = 0; i < 6; ++i)
//{
// data.push_back(i + 1);
//}
//std::cout << "data:[";
//for (auto val : data)
//{
// std::cout << val << ",";
//}
//std::cout << "]\n";
ProductTree pt(data);
DataVector result = pt.Prod2();
//std::cout << "result:[";
//for (auto val : result)
//{
// std::cout << val << ",";
//}
//std::cout << "]\n";
std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';
pt.ops_ = 0;
result = pt.Prod();
//std::cout << "result:[";
//for (auto val : result)
//{
// std::cout << val << ",";
//}
//std::cout << "]\n";
std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';
return 0;
}
I'm adding @nore's algorithm, for completeness. It's really nice, and is the fastest.
class ProductFlat
{
private:
size_t ops_{ 0 };
void InitTables(const DataVector& v, DataVector& left, DataVector& right)
{
if (v.size() < 2)
{
return;
}
left.resize(v.size() - 1);
right.resize(v.size() - 1);
auto l = left.begin();
auto r = right.rbegin();
auto ol = v.begin();
auto or = v.rbegin();
*l = *ol++;
*r = *or++;
if (ol == v.end())
{
return;
}
while (ol + 1 != v.end())
{
ops_ += 2;
*l = *l++ * *ol++;
*r = *r++ * *or++;
}
}
public:
DataVector Prod(const DataVector& v)
{
if (v.size() < 2)
{
return v;
}
DataVector result, left, right;
InitTables(v, left, right);
auto l = left.begin();
auto r = right.begin();
result.push_back(*r++);
while (r != right.end())
{
++ops_;
result.push_back(*l++ * *r++);
}
result.push_back(*l++);
return result;
}
auto Ops() const
{
return ops_;
}
};
Welcome to PPCG! Nice first question! – Erik the Outgolfer – 2017-06-18T17:47:37.403
@EriktheOutgolfer Thank you! – Arthur – 2017-06-18T17:49:31.333
Do the products have to be listed in any particular order? – xnor – 2017-06-18T17:56:40.940
@xnor No. Any order will do. – Arthur – 2017-06-18T17:58:54.987
4May we count multiplying by 1 as free? Otherwise I'd define a custom-multiplication function that does this. – xnor – 2017-06-18T18:22:20.393
For simplicity, all multiplications should be counted in the score, even by 1. – Arthur – 2017-06-18T18:29:27.053
3Would it be against the rules to do a whole bunch of multiplications in parallel by concatenating numbers together with sufficiently many spacer 0 digits? – xnor – 2017-06-18T18:37:50.107
@xnor Yes it would! – Arthur – 2017-06-18T18:39:15.347
Are operations like
– xnor – 2017-06-18T18:48:04.340>=ormaxalso banned? You might want to make this an atomic code golf so people don't try to use language features to get around your restrictions.@xnor I basically don't want to allow any operations that are going to substitute for the arithmetic operations via some trickery. I really want to know how you can do it using a small number of multiplications, subtractions and additions. – Arthur – 2017-06-18T18:50:50.307
1Do the operations such as
+on indices count? If this is the case, does array indexing count as well? (since it is after all syntactic sugar for addition and dereferencing). – nore – 2017-06-18T18:56:44.087I removed the restricted-code tag since my understanding is that atomic-code-golf supersedes it. – xnor – 2017-06-18T18:58:09.230
@nore You can look up/access/read the input elements for free. All the arithmetic operations in your code should be counted however. – Arthur – 2017-06-18T19:00:06.993
@Arthur does this mean a loop has a cost of the number of operations for the counter? – nore – 2017-06-18T19:03:27.987
Are architecture-specific tricks allowed in our answers? – Govind Parmar – 2017-06-18T19:56:13.033
2@nore OK I give in :) Just count arithmetic operations that involve the input in some way. – Arthur – 2017-06-18T20:12:11.813
1Clearly you can do it in
(n-1)*nmultiplications You mean(n-2)*n, right? – Luis Mendo – 2017-06-18T21:16:04.723Does a SIMD operation count as a single operation? – Veedrac – 2017-06-19T02:13:19.317
@Veedrac Not for this challenge, sorry. – Arthur – 2017-06-19T08:25:45.000
Maybe I'm being thick, but what does it mean to multiply two or more sets? No definition of set that I know has a multiply operation. Perhaps you could give a worked example for what the result would be for a small input array? – Toby Speight – 2017-06-19T17:05:45.213
@TobySpeight If the input has three number
1,2,3, then the output is three numbers6 = 2*3,3 = 1*3and2 = 1*2. Does that help? – Arthur – 2017-06-19T17:15:41.9331Oh, so you're asking for a set of outputs - no wonder I was confused. The way it's worded in the question suggests you are looking for
(2,3) * (1,3) * (1,2)- perhaps it could be edited to include your helpful example? – Toby Speight – 2017-06-19T17:21:31.257If this was a simple code golf, I would submit this Perl 6 one
{.combinations(.end).map: *.reduce: &prefix:<[*]>}– Brad Gilbert b2gills – 2017-06-19T18:26:12.273