diff options
author | alex-sh <alex-sh@yandex-team.ru> | 2022-02-10 16:50:03 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:50:03 +0300 |
commit | 88ee78b1a163eaddee7e880ac73943456040fce0 (patch) | |
tree | 5d5cb817648f650d76cf1076100726fd9b8448e8 /library/cpp/linear_regression/linear_regression_ut.cpp | |
parent | 3196904c9f5bf7aff7374eeadcb0671589581f61 (diff) | |
download | ydb-88ee78b1a163eaddee7e880ac73943456040fce0.tar.gz |
Restoring authorship annotation for <alex-sh@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/linear_regression/linear_regression_ut.cpp')
-rw-r--r-- | library/cpp/linear_regression/linear_regression_ut.cpp | 522 |
1 files changed, 261 insertions, 261 deletions
diff --git a/library/cpp/linear_regression/linear_regression_ut.cpp b/library/cpp/linear_regression/linear_regression_ut.cpp index 01d2a7e761..e71a16b67a 100644 --- a/library/cpp/linear_regression/linear_regression_ut.cpp +++ b/library/cpp/linear_regression/linear_regression_ut.cpp @@ -1,303 +1,303 @@ #include <library/cpp/linear_regression/linear_regression.h> #include <library/cpp/testing/unittest/registar.h> - -#include <util/generic/vector.h> -#include <util/generic/ymath.h> + +#include <util/generic/vector.h> +#include <util/generic/ymath.h> #include <util/random/random.h> - -#include <util/system/defaults.h> - -namespace { - void ValueIsCorrect(const double value, const double expectedValue, double possibleRelativeError) { - UNIT_ASSERT_DOUBLES_EQUAL(value, expectedValue, possibleRelativeError * expectedValue); - } -} - + +#include <util/system/defaults.h> + +namespace { + void ValueIsCorrect(const double value, const double expectedValue, double possibleRelativeError) { + UNIT_ASSERT_DOUBLES_EQUAL(value, expectedValue, possibleRelativeError * expectedValue); + } +} + Y_UNIT_TEST_SUITE(TLinearRegressionTest) { Y_UNIT_TEST(MeanAndDeviationTest) { TVector<double> arguments; TVector<double> weights; - - const size_t argumentsCount = 100; - for (size_t i = 0; i < argumentsCount; ++i) { - arguments.push_back(i); - weights.push_back(i); - } - - TDeviationCalculator deviationCalculator; - TMeanCalculator meanCalculator; - for (size_t i = 0; i < arguments.size(); ++i) { - meanCalculator.Add(arguments[i], weights[i]); - deviationCalculator.Add(arguments[i], weights[i]); - } - + + const size_t argumentsCount = 100; + for (size_t i = 0; i < argumentsCount; ++i) { + arguments.push_back(i); + weights.push_back(i); + } + + TDeviationCalculator deviationCalculator; + TMeanCalculator meanCalculator; + for (size_t i = 0; i < arguments.size(); ++i) { + meanCalculator.Add(arguments[i], weights[i]); + deviationCalculator.Add(arguments[i], weights[i]); + } + double actualMean = InnerProduct(arguments, weights) / Accumulate(weights, 0.0); - double actualDeviation = 0.; - for (size_t i = 0; i < arguments.size(); ++i) { - double deviation = arguments[i] - actualMean; - actualDeviation += deviation * deviation * weights[i]; - } - - UNIT_ASSERT(IsValidFloat(meanCalculator.GetMean())); - UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), actualMean, 1e-10); - - UNIT_ASSERT(IsValidFloat(deviationCalculator.GetDeviation())); - UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), deviationCalculator.GetMean(), 0); - - UNIT_ASSERT(IsValidFloat(meanCalculator.GetSumWeights())); - UNIT_ASSERT(IsValidFloat(deviationCalculator.GetSumWeights())); - UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetSumWeights(), deviationCalculator.GetSumWeights(), 0); + double actualDeviation = 0.; + for (size_t i = 0; i < arguments.size(); ++i) { + double deviation = arguments[i] - actualMean; + actualDeviation += deviation * deviation * weights[i]; + } + + UNIT_ASSERT(IsValidFloat(meanCalculator.GetMean())); + UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), actualMean, 1e-10); + + UNIT_ASSERT(IsValidFloat(deviationCalculator.GetDeviation())); + UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), deviationCalculator.GetMean(), 0); + + UNIT_ASSERT(IsValidFloat(meanCalculator.GetSumWeights())); + UNIT_ASSERT(IsValidFloat(deviationCalculator.GetSumWeights())); + UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetSumWeights(), deviationCalculator.GetSumWeights(), 0); UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetSumWeights(), Accumulate(weights, 0.0), 0); - - ValueIsCorrect(deviationCalculator.GetDeviation(), actualDeviation, 1e-5); - - TMeanCalculator checkRemovingMeanCalculator; - TDeviationCalculator checkRemovingDeviationCalculator; - - const size_t argumentsToRemoveCount = argumentsCount / 3; - for (size_t i = 0; i < argumentsCount; ++i) { - if (i < argumentsToRemoveCount) { - meanCalculator.Remove(arguments[i], weights[i]); - deviationCalculator.Remove(arguments[i], weights[i]); - } else { - checkRemovingMeanCalculator.Add(arguments[i], weights[i]); - checkRemovingDeviationCalculator.Add(arguments[i], weights[i]); - } - } - - UNIT_ASSERT(IsValidFloat(meanCalculator.GetMean())); - UNIT_ASSERT(IsValidFloat(checkRemovingMeanCalculator.GetMean())); - - UNIT_ASSERT(IsValidFloat(deviationCalculator.GetDeviation())); - UNIT_ASSERT(IsValidFloat(checkRemovingDeviationCalculator.GetDeviation())); - - UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), deviationCalculator.GetMean(), 0); - UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), checkRemovingMeanCalculator.GetMean(), 1e-10); - - ValueIsCorrect(deviationCalculator.GetDeviation(), checkRemovingDeviationCalculator.GetDeviation(), 1e-5); - } - + + ValueIsCorrect(deviationCalculator.GetDeviation(), actualDeviation, 1e-5); + + TMeanCalculator checkRemovingMeanCalculator; + TDeviationCalculator checkRemovingDeviationCalculator; + + const size_t argumentsToRemoveCount = argumentsCount / 3; + for (size_t i = 0; i < argumentsCount; ++i) { + if (i < argumentsToRemoveCount) { + meanCalculator.Remove(arguments[i], weights[i]); + deviationCalculator.Remove(arguments[i], weights[i]); + } else { + checkRemovingMeanCalculator.Add(arguments[i], weights[i]); + checkRemovingDeviationCalculator.Add(arguments[i], weights[i]); + } + } + + UNIT_ASSERT(IsValidFloat(meanCalculator.GetMean())); + UNIT_ASSERT(IsValidFloat(checkRemovingMeanCalculator.GetMean())); + + UNIT_ASSERT(IsValidFloat(deviationCalculator.GetDeviation())); + UNIT_ASSERT(IsValidFloat(checkRemovingDeviationCalculator.GetDeviation())); + + UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), deviationCalculator.GetMean(), 0); + UNIT_ASSERT_DOUBLES_EQUAL(meanCalculator.GetMean(), checkRemovingMeanCalculator.GetMean(), 1e-10); + + ValueIsCorrect(deviationCalculator.GetDeviation(), checkRemovingDeviationCalculator.GetDeviation(), 1e-5); + } + Y_UNIT_TEST(CovariationTest) { TVector<double> firstValues; TVector<double> secondValues; TVector<double> weights; - - const size_t argumentsCount = 100; - for (size_t i = 0; i < argumentsCount; ++i) { - firstValues.push_back(i); - secondValues.push_back(i * i); - weights.push_back(i); - } - - TCovariationCalculator covariationCalculator; - for (size_t i = 0; i < argumentsCount; ++i) { - covariationCalculator.Add(firstValues[i], secondValues[i], weights[i]); - } - + + const size_t argumentsCount = 100; + for (size_t i = 0; i < argumentsCount; ++i) { + firstValues.push_back(i); + secondValues.push_back(i * i); + weights.push_back(i); + } + + TCovariationCalculator covariationCalculator; + for (size_t i = 0; i < argumentsCount; ++i) { + covariationCalculator.Add(firstValues[i], secondValues[i], weights[i]); + } + const double firstValuesMean = InnerProduct(firstValues, weights) / Accumulate(weights, 0.0); const double secondValuesMean = InnerProduct(secondValues, weights) / Accumulate(weights, 0.0); - - double actualCovariation = 0.; - for (size_t i = 0; i < argumentsCount; ++i) { - actualCovariation += (firstValues[i] - firstValuesMean) * (secondValues[i] - secondValuesMean) * weights[i]; - } - - UNIT_ASSERT(IsValidFloat(covariationCalculator.GetCovariation())); - UNIT_ASSERT(IsValidFloat(covariationCalculator.GetFirstValueMean())); - UNIT_ASSERT(IsValidFloat(covariationCalculator.GetSecondValueMean())); - - UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator.GetFirstValueMean(), firstValuesMean, 1e-10); - UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator.GetSecondValueMean(), secondValuesMean, 1e-10); - - UNIT_ASSERT(IsValidFloat(covariationCalculator.GetSumWeights())); + + double actualCovariation = 0.; + for (size_t i = 0; i < argumentsCount; ++i) { + actualCovariation += (firstValues[i] - firstValuesMean) * (secondValues[i] - secondValuesMean) * weights[i]; + } + + UNIT_ASSERT(IsValidFloat(covariationCalculator.GetCovariation())); + UNIT_ASSERT(IsValidFloat(covariationCalculator.GetFirstValueMean())); + UNIT_ASSERT(IsValidFloat(covariationCalculator.GetSecondValueMean())); + + UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator.GetFirstValueMean(), firstValuesMean, 1e-10); + UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator.GetSecondValueMean(), secondValuesMean, 1e-10); + + UNIT_ASSERT(IsValidFloat(covariationCalculator.GetSumWeights())); UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator.GetSumWeights(), Accumulate(weights, 0.0), 0); - - ValueIsCorrect(covariationCalculator.GetCovariation(), actualCovariation, 1e-5); - - TCovariationCalculator checkRemovingCovariationCalculator; - - const size_t argumentsToRemoveCount = argumentsCount / 3; - for (size_t i = 0; i < argumentsCount; ++i) { - if (i < argumentsToRemoveCount) { - covariationCalculator.Remove(firstValues[i], secondValues[i], weights[i]); - } else { - checkRemovingCovariationCalculator.Add(firstValues[i], secondValues[i], weights[i]); - } - } - - ValueIsCorrect(covariationCalculator.GetCovariation(), checkRemovingCovariationCalculator.GetCovariation(), 1e-5); - } - - template <typename TSLRSolverType> - void SLRTest() { + + ValueIsCorrect(covariationCalculator.GetCovariation(), actualCovariation, 1e-5); + + TCovariationCalculator checkRemovingCovariationCalculator; + + const size_t argumentsToRemoveCount = argumentsCount / 3; + for (size_t i = 0; i < argumentsCount; ++i) { + if (i < argumentsToRemoveCount) { + covariationCalculator.Remove(firstValues[i], secondValues[i], weights[i]); + } else { + checkRemovingCovariationCalculator.Add(firstValues[i], secondValues[i], weights[i]); + } + } + + ValueIsCorrect(covariationCalculator.GetCovariation(), checkRemovingCovariationCalculator.GetCovariation(), 1e-5); + } + + template <typename TSLRSolverType> + void SLRTest() { TVector<double> arguments; TVector<double> weights; TVector<double> goals; - - const double factor = 2.; - const double intercept = 105.; - const double randomError = 0.01; - - const size_t argumentsCount = 10; - for (size_t i = 0; i < argumentsCount; ++i) { - arguments.push_back(i); - weights.push_back(i); - goals.push_back(arguments.back() * factor + intercept + 2 * (i % 2 - 0.5) * randomError); - } - - TSLRSolverType slrSolver; - for (size_t i = 0; i < argumentsCount; ++i) { - slrSolver.Add(arguments[i], goals[i], weights[i]); - } - - for (double regularizationThreshold = 0.; regularizationThreshold < 0.05; regularizationThreshold += 0.01) { - double solutionFactor, solutionIntercept; - slrSolver.Solve(solutionFactor, solutionIntercept, regularizationThreshold); - - double predictedSumSquaredErrors = slrSolver.SumSquaredErrors(regularizationThreshold); - - UNIT_ASSERT(IsValidFloat(solutionFactor)); - UNIT_ASSERT(IsValidFloat(solutionIntercept)); - UNIT_ASSERT(IsValidFloat(predictedSumSquaredErrors)); - - UNIT_ASSERT_DOUBLES_EQUAL(solutionFactor, factor, 1e-2); - UNIT_ASSERT_DOUBLES_EQUAL(solutionIntercept, intercept, 1e-2); - - double sumSquaredErrors = 0.; - for (size_t i = 0; i < argumentsCount; ++i) { - double error = goals[i] - arguments[i] * solutionFactor - solutionIntercept; - sumSquaredErrors += error * error * weights[i]; - } - - if (!regularizationThreshold) { + + const double factor = 2.; + const double intercept = 105.; + const double randomError = 0.01; + + const size_t argumentsCount = 10; + for (size_t i = 0; i < argumentsCount; ++i) { + arguments.push_back(i); + weights.push_back(i); + goals.push_back(arguments.back() * factor + intercept + 2 * (i % 2 - 0.5) * randomError); + } + + TSLRSolverType slrSolver; + for (size_t i = 0; i < argumentsCount; ++i) { + slrSolver.Add(arguments[i], goals[i], weights[i]); + } + + for (double regularizationThreshold = 0.; regularizationThreshold < 0.05; regularizationThreshold += 0.01) { + double solutionFactor, solutionIntercept; + slrSolver.Solve(solutionFactor, solutionIntercept, regularizationThreshold); + + double predictedSumSquaredErrors = slrSolver.SumSquaredErrors(regularizationThreshold); + + UNIT_ASSERT(IsValidFloat(solutionFactor)); + UNIT_ASSERT(IsValidFloat(solutionIntercept)); + UNIT_ASSERT(IsValidFloat(predictedSumSquaredErrors)); + + UNIT_ASSERT_DOUBLES_EQUAL(solutionFactor, factor, 1e-2); + UNIT_ASSERT_DOUBLES_EQUAL(solutionIntercept, intercept, 1e-2); + + double sumSquaredErrors = 0.; + for (size_t i = 0; i < argumentsCount; ++i) { + double error = goals[i] - arguments[i] * solutionFactor - solutionIntercept; + sumSquaredErrors += error * error * weights[i]; + } + + if (!regularizationThreshold) { UNIT_ASSERT(predictedSumSquaredErrors < Accumulate(weights, 0.0) * randomError * randomError); - } - UNIT_ASSERT_DOUBLES_EQUAL(predictedSumSquaredErrors, sumSquaredErrors, 1e-8); - } - } - + } + UNIT_ASSERT_DOUBLES_EQUAL(predictedSumSquaredErrors, sumSquaredErrors, 1e-8); + } + } + Y_UNIT_TEST(FastSLRTest) { - SLRTest<TFastSLRSolver>(); - } - + SLRTest<TFastSLRSolver>(); + } + Y_UNIT_TEST(KahanSLRTest) { - SLRTest<TKahanSLRSolver>(); - } - + SLRTest<TKahanSLRSolver>(); + } + Y_UNIT_TEST(SLRTest) { - SLRTest<TSLRSolver>(); - } - - template <typename TLinearRegressionSolverType> - void LinearRegressionTest() { - const size_t featuresCount = 10; - const size_t instancesCount = 10000; - const double randomError = 0.01; - + SLRTest<TSLRSolver>(); + } + + template <typename TLinearRegressionSolverType> + void LinearRegressionTest() { + const size_t featuresCount = 10; + const size_t instancesCount = 10000; + const double randomError = 0.01; + TVector<double> coefficients; - for (size_t featureNumber = 0; featureNumber < featuresCount; ++featureNumber) { - coefficients.push_back(featureNumber); - } - const double intercept = 10; - + for (size_t featureNumber = 0; featureNumber < featuresCount; ++featureNumber) { + coefficients.push_back(featureNumber); + } + const double intercept = 10; + TVector<TVector<double>> featuresMatrix; TVector<double> goals; TVector<double> weights; - - for (size_t instanceNumber = 0; instanceNumber < instancesCount; ++instanceNumber) { + + for (size_t instanceNumber = 0; instanceNumber < instancesCount; ++instanceNumber) { TVector<double> features; - for (size_t featureNumber = 0; featureNumber < featuresCount; ++featureNumber) { + for (size_t featureNumber = 0; featureNumber < featuresCount; ++featureNumber) { features.push_back(RandomNumber<double>()); - } - featuresMatrix.push_back(features); - - const double goal = InnerProduct(coefficients, features) + intercept + 2 * (instanceNumber % 2 - 0.5) * randomError; - goals.push_back(goal); - weights.push_back(instanceNumber); - } - - TLinearRegressionSolverType lrSolver; - for (size_t instanceNumber = 0; instanceNumber < instancesCount; ++instanceNumber) { - lrSolver.Add(featuresMatrix[instanceNumber], goals[instanceNumber], weights[instanceNumber]); - } - const TLinearModel model = lrSolver.Solve(); - - for (size_t featureNumber = 0; featureNumber < featuresCount; ++featureNumber) { - UNIT_ASSERT_DOUBLES_EQUAL(model.GetCoefficients()[featureNumber], coefficients[featureNumber], 1e-2); - } - UNIT_ASSERT_DOUBLES_EQUAL(model.GetIntercept(), intercept, 1e-2); - + } + featuresMatrix.push_back(features); + + const double goal = InnerProduct(coefficients, features) + intercept + 2 * (instanceNumber % 2 - 0.5) * randomError; + goals.push_back(goal); + weights.push_back(instanceNumber); + } + + TLinearRegressionSolverType lrSolver; + for (size_t instanceNumber = 0; instanceNumber < instancesCount; ++instanceNumber) { + lrSolver.Add(featuresMatrix[instanceNumber], goals[instanceNumber], weights[instanceNumber]); + } + const TLinearModel model = lrSolver.Solve(); + + for (size_t featureNumber = 0; featureNumber < featuresCount; ++featureNumber) { + UNIT_ASSERT_DOUBLES_EQUAL(model.GetCoefficients()[featureNumber], coefficients[featureNumber], 1e-2); + } + UNIT_ASSERT_DOUBLES_EQUAL(model.GetIntercept(), intercept, 1e-2); + const double expectedSumSquaredErrors = randomError * randomError * Accumulate(weights, 0.0); - UNIT_ASSERT_DOUBLES_EQUAL(lrSolver.SumSquaredErrors(), expectedSumSquaredErrors, expectedSumSquaredErrors * 0.01); - } - + UNIT_ASSERT_DOUBLES_EQUAL(lrSolver.SumSquaredErrors(), expectedSumSquaredErrors, expectedSumSquaredErrors * 0.01); + } + Y_UNIT_TEST(FastLRTest) { - LinearRegressionTest<TFastLinearRegressionSolver>(); - } - + LinearRegressionTest<TFastLinearRegressionSolver>(); + } + Y_UNIT_TEST(LRTest) { - LinearRegressionTest<TLinearRegressionSolver>(); - } - - void TransformationTest(const ETransformationType transformationType, const size_t pointsCount) { + LinearRegressionTest<TLinearRegressionSolver>(); + } + + void TransformationTest(const ETransformationType transformationType, const size_t pointsCount) { TVector<float> arguments; TVector<float> goals; - - const double regressionFactor = 10.; - const double regressionIntercept = 100; - - const double featureOffset = -1.5; - const double featureNormalizer = 15; - - const double left = -100.; - const double right = +100.; - const double step = (right - left) / pointsCount; - - for (double argument = left; argument <= right; argument += step) { - const double goal = regressionIntercept + regressionFactor * (argument - featureOffset) / (fabs(argument - featureOffset) + featureNormalizer); - - arguments.push_back(argument); - goals.push_back(goal); - } - - TFastFeaturesTransformerLearner learner(transformationType); - for (size_t instanceNumber = 0; instanceNumber < arguments.size(); ++instanceNumber) { - learner.Add(arguments[instanceNumber], goals[instanceNumber]); - } - TFeaturesTransformer transformer = learner.Solve(); - - double sse = 0.; - for (size_t instanceNumber = 0; instanceNumber < arguments.size(); ++instanceNumber) { - const double error = transformer.Transformation(arguments[instanceNumber]) - goals[instanceNumber]; - sse += error * error; - } - const double rmse = sqrt(sse / arguments.size()); - UNIT_ASSERT_DOUBLES_EQUAL(rmse, 0., 1e-3); - } - + + const double regressionFactor = 10.; + const double regressionIntercept = 100; + + const double featureOffset = -1.5; + const double featureNormalizer = 15; + + const double left = -100.; + const double right = +100.; + const double step = (right - left) / pointsCount; + + for (double argument = left; argument <= right; argument += step) { + const double goal = regressionIntercept + regressionFactor * (argument - featureOffset) / (fabs(argument - featureOffset) + featureNormalizer); + + arguments.push_back(argument); + goals.push_back(goal); + } + + TFastFeaturesTransformerLearner learner(transformationType); + for (size_t instanceNumber = 0; instanceNumber < arguments.size(); ++instanceNumber) { + learner.Add(arguments[instanceNumber], goals[instanceNumber]); + } + TFeaturesTransformer transformer = learner.Solve(); + + double sse = 0.; + for (size_t instanceNumber = 0; instanceNumber < arguments.size(); ++instanceNumber) { + const double error = transformer.Transformation(arguments[instanceNumber]) - goals[instanceNumber]; + sse += error * error; + } + const double rmse = sqrt(sse / arguments.size()); + UNIT_ASSERT_DOUBLES_EQUAL(rmse, 0., 1e-3); + } + Y_UNIT_TEST(SigmaTest100) { - TransformationTest(ETransformationType::TT_SIGMA, 100); - } - + TransformationTest(ETransformationType::TT_SIGMA, 100); + } + Y_UNIT_TEST(SigmaTest1000) { - TransformationTest(ETransformationType::TT_SIGMA, 1000); - } - + TransformationTest(ETransformationType::TT_SIGMA, 1000); + } + Y_UNIT_TEST(SigmaTest10000) { - TransformationTest(ETransformationType::TT_SIGMA, 10000); - } - + TransformationTest(ETransformationType::TT_SIGMA, 10000); + } + Y_UNIT_TEST(SigmaTest100000) { - TransformationTest(ETransformationType::TT_SIGMA, 100000); - } - + TransformationTest(ETransformationType::TT_SIGMA, 100000); + } + Y_UNIT_TEST(SigmaTest1000000) { - TransformationTest(ETransformationType::TT_SIGMA, 1000000); - } - + TransformationTest(ETransformationType::TT_SIGMA, 1000000); + } + Y_UNIT_TEST(SigmaTest10000000) { - TransformationTest(ETransformationType::TT_SIGMA, 10000000); - } + TransformationTest(ETransformationType::TT_SIGMA, 10000000); + } Y_UNIT_TEST(ResetCalculatorTest) { TVector<double> arguments; @@ -371,4 +371,4 @@ Y_UNIT_TEST_SUITE(TLinearRegressionTest) { UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator1.GetCovariation(), covariationCalculator2.GetCovariation(), eps); UNIT_ASSERT_DOUBLES_EQUAL(covariationCalculator1.GetSumWeights(), covariationCalculator2.GetSumWeights(), eps); } -} +} |