felipecrv commented on code in PR #35345:
URL: https://github.com/apache/arrow/pull/35345#discussion_r1395849677
##########
cpp/src/arrow/testing/random.cc:
##########
@@ -608,6 +609,218 @@ std::shared_ptr<Array>
OffsetsFromLengthsArray(OffsetArrayType* lengths,
std::make_shared<typename OffsetArrayType::TypeClass>(), size, buffers,
null_count);
return std::make_shared<OffsetArrayType>(array_data);
}
+
+// Helper for RandomArrayGenerator::ArrayOf: extract some C value from
+// a given metadata key.
+template <typename T, typename ArrowType = typename CTypeTraits<T>::ArrowType>
+enable_if_parameter_free<ArrowType, T> GetMetadata(const KeyValueMetadata*
metadata,
+ const std::string& key,
+ T default_value) {
+ if (!metadata) return default_value;
+ const auto index = metadata->FindKey(key);
+ if (index < 0) return default_value;
+ const auto& value = metadata->value(index);
+ T output{};
+ if (!internal::ParseValue<ArrowType>(value.data(), value.length(), &output))
{
+ ABORT_NOT_OK(Status::Invalid("Could not parse ", key, " = ", value, " as ",
+ ArrowType::type_name()));
+ }
+ return output;
+}
+
+/// \brief Shuffle a list-view array in place using the Fisher–Yates algorithm
[1].
+///
+/// [1]
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
+///
+/// \param[in] seed The seed for the random number generator
+/// \param[in,out] data The array to shuffle
+template <typename ListViewType>
+void ShuffleListViewDataInPlace(SeedType seed, ArrayData& data) {
+ DCHECK_EQ(data.type->id(), ListViewType::type_id);
+ using offset_type = typename ListViewType::offset_type;
+
+ auto* validity = data.GetMutableValues<uint8_t>(0, 0);
+ auto* offsets = data.GetMutableValues<offset_type>(1);
+ auto* sizes = data.GetMutableValues<offset_type>(2);
+
+ pcg32_fast rng(seed);
+ using UniformDist = std::uniform_int_distribution<int64_t>;
+ UniformDist dist;
+ for (int64_t i = data.length - 1; i > 0; --i) {
+ const auto j = dist(rng, UniformDist::param_type(0, i));
+ if (ARROW_PREDICT_TRUE(i != j)) {
+ // Swap validity bits
+ if (validity) {
+ const bool valid_i = bit_util::GetBit(validity, data.offset + i);
+ const bool valid_j = bit_util::GetBit(validity, data.offset + i);
+ if (valid_i != valid_j) {
+ bit_util::SetBitTo(validity, data.offset + i, valid_j);
+ bit_util::SetBitTo(validity, data.offset + j, valid_i);
+ }
+ }
+ // Swap offsets and sizes
+ std::swap(offsets[i], offsets[j]);
+ std::swap(sizes[i], sizes[j]);
+ }
+ }
+}
+
+/// \brief Generate the list-view offsets based on a random buffer of sizes.
+///
+/// The sizes buffer is an input of this function, but when force_empty_nulls
is true,
+/// some values on the sizes buffer can be set to 0.
+///
+/// When sparsity is 0.0, the list-view spans are perfectly packed one after
the
+/// other. If sparsity is greater than 0.0, the list-view spans are set apart
+/// from each other in proportion to the sparsity value and size of each
+/// list-view. A negative sparsity means each list-view shares a fraction of
the
+/// values used by the previous list-view.
+///
+/// For instance, a sparsity of -1.0 means the values array will only need
enough values
+/// for the largest list-view with all the other list-views spanning some of
these same
+/// values.
+///
+/// \param[in] seed The seed for the random number generator
+/// \param[in,out] mutable_sizes_array The array of sizes to use
+/// \param[in] force_empty_nulls Whether to force null list-view sizes to be 0
+/// \param[in] zero_undefined_offsets Whether to zero the offsets of
list-views that have
+/// 0 set as the size
+/// \param[in] sparsity The sparsity of the generated list-view offsets
+/// \param[out] out_max_view_end The maximum value of the end of a list-view
+template <typename OffsetArrayType, typename offset_type>
+std::shared_ptr<Array> ViewOffsetsFromLengthsArray(
+ SeedType seed, OffsetArrayType& mutable_sizes_array, bool
force_empty_nulls,
+ bool zero_undefined_offsets, double sparsity, int64_t* out_max_view_end,
+ int64_t alignment, MemoryPool* memory_pool) {
+ using TypeClass = typename OffsetArrayType::TypeClass;
+
+ auto* sizes = mutable_sizes_array.data()->template
GetMutableValues<offset_type>(1);
+
+ BufferVector buffers{2};
+ buffers[0] = NULLPTR; // sizes can have nulls, offsets don't have to
+ buffers[1] = *AllocateBuffer(sizeof(offset_type) *
mutable_sizes_array.length(),
+ alignment, memory_pool);
+ auto offsets = buffers[1]->mutable_data_as<offset_type>();
+
+ double offset_base = 0.0;
+ offset_type max_view_end = 0;
+ for (int64_t i = 0; i < mutable_sizes_array.length(); ++i) {
+ const auto offset = static_cast<offset_type>(std::llround(offset_base));
+ if (mutable_sizes_array.IsNull(i)) {
+ if (force_empty_nulls) {
+ sizes[i] = 0;
+ }
+ offsets[i] = zero_undefined_offsets ? 0 : offset;
+ } else {
+ if (sizes[i] == 0) {
+ offsets[i] = zero_undefined_offsets ? 0 : offset;
+ } else {
+ offsets[i] = offset;
+ DCHECK_LT(offset, std::numeric_limits<offset_type>::max() - sizes[i]);
+ offset_base = std::max(0.0, offset_base + (sparsity * sizes[i]));
+ }
+ }
+ max_view_end = std::max(max_view_end, offsets[i] + sizes[i]);
+ }
+ *out_max_view_end = max_view_end;
+
+ auto array_data =
+ ArrayData::Make(TypeTraits<TypeClass>::type_singleton(),
+ mutable_sizes_array.length(), std::move(buffers),
/*null_count=*/0);
+ return std::make_shared<OffsetArrayType>(std::move(array_data));
+}
+
+template <typename ArrayType, typename RAG>
+Result<std::shared_ptr<Array>> ArrayOfListView(RAG& self, const Field& field,
Review Comment:
I'm removing the `sparsity` parameter, but adding coverage to this makes
controlling the size of the list-views an issue for benchmarks (that want sizes
to follow a certain distribution of sizes).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
